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

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^{n} 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^{n} by computing x^{(n/2)} * x^{(n/2)}. If power of x is odd, we can compute x^{n} 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_{2}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
^{n}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
^{n}to x^{n/2}, so it needs log_{2}n steps. - So running time of divide and conquer approach is O(log
_{2 }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_{2}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^{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}) + 3

.

.

After k iterations,

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

Binary tree created by binary search can have maximum height log_{2}n

So, k = log_{2}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_{2}n

T(n) = O(log_{2}n)

### Example

**Example: Show the steps to compute x ^{13} using the divide and conquer approach.**

**Solution:**

Here, n = 13 (odd), so sub problems would be, x^{13} = x^{6} * x^{6} * x

Now, n = 6 (even), so sub problems would be, x^{6} = x^{3} * x^{3}

Now, n = 3 (odd), so sub problems would be, x^{3} = x * x * x

Let us consider 2^{13}

In first stage of division: 2^{13} = 2^{6} * 2^{6} * 2 … (1)

In second stage of division: 2^{6} = 2^{3} * 2^{3} … (2)

In third stage of division: 2^{3} = 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^{3} = 2 * 2 * 2 = 8

From equation (2), 2^{6} = 2^{3} * 2^{3} = 8 * 8 = 64

From equation (1), 2^{13} = 2^{6} * 2^{6} * 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