# 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 xn is very simple. Conventional approach would perform x * x * x … * x total (n – 1) number of times to find xn. 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 x13 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 213:

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 xn is achieved by creating sub problems of size xn/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 xn by computing x(n/2) * x(n/2). If power of x is odd, we can compute xn 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 log2n.

### 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 xn to xn-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 xn to xn/2, so it needs log2n steps.
• So running time of divide and conquer approach is O(log2 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(log2n)

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/22) + 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/23)  + 3

.

.

After k iterations,

T(n)   =   T(nk) + k

Binary tree created by binary search can have maximum height log2n

So, k = log2n ⇒ n = 2k

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

= T(1) + k

From base case of recurrence,

T(n) = 1 + k = 1 + log2n

T(n) = O(log2n)

### Example

Example: Show the steps to compute x13 using the divide and conquer approach.

Solution:

Here, n = 13 (odd), so sub problems would be, x13 = x6 * x6 * x

Now, n = 6 (even), so sub problems would be, x6 = x3 * x3

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

Let us consider 213

In first stage of division: 213 = 26 * 26 * 2 … (1)

In second stage of division: 26 = 23 * 23 … (2)

In third stage of division: 23 = 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), 23 = 2 * 2 * 2 = 8

From equation (2), 26 = 23 * 23 = 8 * 8 = 64

From equation (1), 213 = 26 * 26 * 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.