Exponential Problem solving using Divide and Conquer

Traditional Way of solving Exponential Problem

Exponential problem is very common in computer science. The traditional way of finding exponential xⁿ is very simple. Conventional approach would perform x * x * x … * x total (n – 1) number of times to find xⁿ. This algorithm runs in the linear order of n, so it does not scale well.

Algorithm

The algorithm for finding exponent using a conventional approach is shown below:

Algorithm EXPONENT(x, n)
// we want to find n power of x

exp  ← 1
for i ← 1 to n do
    exp  ← exp *  x
end

Example

Problem: Show the steps to compute x¹³ using traditional approach

Solution:

C code for solving the algorithm is shown below. Its iterative process. In every iteration, x is multiplied with previous answer.

exp = 1;
n = 13;
for(i=1; i<=n; i++)
{
  exp = exp * x;
}
printf("x power n = ", exp);

Let us try to solve 2¹³:

As per the above code

Initially, exp = 1;

Iteration 1: exp = exp * x = 1 * 2 = 2

Iteration 2: exp = exp * x = 2 * 2 = 4

Iteration 3: exp = exp * x = 4 * 2 = 8

Iteration 4: exp = exp * x = 8 * 2 = 16

Iteration 5: exp = exp * x = 16 * 2 = 32

Iteration 6: exp = exp * x = 32 * 2 = 64

Iteration 7: exp = exp * x = 64 * 2 = 128

Iteration 8: exp = exp * x = 128 * 2 = 256

Iteration 9: exp = exp * x = 256 * 2 = 512

Iteration 10: exp = exp * x = 512 * 2 = 1024

Iteration 11: exp = exp * x = 1024 * 2 = 2048

Iteration 12: exp = exp * x = 2048 * 2 = 4096

Iteration 13: exp = exp * x = 4096 * 2 = 8192

This algorithm runs in O(n) time. We can improve running time of algorithm by making use of divide and conquer. Divide and conquer algorithm for finding exponent is described here :

Divide and Conquer Approach for solving Exponential Problem

In divide and conquer approach, exponential of xⁿ is achieved by creating sub problems of size x^n/2. They are sub problems are divided recursively until they hit to the power 1. The recursive solution to the problem is depicted in following equation

If power of x is even, then simply we can find xⁿ by computing x^(n/2) * x^(n/2). If power of x is odd, we can compute xⁿ by solving x^((n-1)/2) * x^((n-1)/2) * x.

Problem size reduces by factor of 2 in every recursive call and very soon it hits to base case. This division of problem creates tree of height log₂n.

Algorithm

Algorithm EXPONENT_DC(x, n)
// we want to find n power of x

if n == 0 then
    return 1
else
    m ← EXPONENT_DC(x, n/2)
    if n%2 == 0 then
        return m*m      // if n is even
    else
        return m*m*x    // if n is odd
    end
end

Complexity Analysis of Exponential Problem

• In the traditional method, each step partial solution is multiplied by x and hence problem size reduces from xⁿ to x^n-1, so it needs n steps and hence its running time is O(n).
•  While in the case of divide and conquer strategy, during each step, a partial solution is multiplied by itself and hence problem size reduces from xⁿ to x^n/2, so it needs log₂n steps.
• So running time of divide and conquer approach is O(log₂ n)

The recurrence relation for exponential problem using divide and conquer is given as,

T(n) = T(n/2) + 1

Using iterative method, it is not difficult to show that the solution to this equation would be O(log₂n)

Only one multiplication is needed when n = 2, that’s the trivial case. This is the boundary condition for recurrence. Let us solve this by iterative approach,

T (n) = T(n/2)  + 1 …(1)

Substitute n by n/2 in Equation (1) to find T(n/2)

T(n/2) = T(n/4) + 1 …(2)

Substitute value of T(n/2) in Equation (1),

T(n) = T(n/2²) + 1 …(3)

Substitute n by n/2 in Equation (2) to find T(n/4),

T(n/4) = T(n/8) + 1

Substitute value of T(n/4) in Equation (3),           

T(n)  = T(n/2³)  + 3

.

 .

After k iterations,

T(n)   =   T(n^k) + k

Binary tree created by binary search can have maximum height log₂n

So, k = log₂n ⇒ n = 2^k

T(n) = T(2^k/2^k)  + k

= T(1) + k

From base case of recurrence,

T(n) = 1 + k = 1 + log₂n

T(n) = O(log₂n)

Example

Example: Show the steps to compute x¹³ using the divide and conquer approach.

Solution:

Here, n = 13 (odd), so sub problems would be, x¹³ = x⁶ * x⁶ * x

Now, n = 6 (even), so sub problems would be, x⁶ = x³ * x³

Now, n = 3 (odd), so sub problems would be, x³ = x * x * x

Let us consider 2¹³

In first stage of division: 2¹³ = 2⁶ * 2⁶ * 2 … (1)

In second stage of division: 2⁶ = 2³ * 2³ … (2)

In third stage of division: 2³ = 2 * 2 * 2 … (3)

For this problem, n =1,

now this smallest sub problems will be solved and the result will be passed to parent problem

From equation (3), 2³ = 2 * 2 * 2 = 8

From equation (2), 2⁶ = 2³ * 2³ = 8 * 8 = 64

From equation (1), 2¹³ = 2⁶ * 2⁶ * 2 = 64 * 64 * 2 = 8192.

Traditional approach would have done this computation in 13 iteration, where as divide and conquer has solved it in just 3 iterations.

Some Popular Problems Solved using Divide and Conquer

• Linear Search
• Binary Search
• Convex Hull
• Max-Min Problem
• Larger Integer Multiplication
• Strassen’s Matrix Multiplication
• Finding Exponent Problem
• Merge Sort
• Quick Sort

 

---

Additional Reading: Read More