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

Algorithm for finding exponent using 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

exponential problem using divide and conquer

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

Problem: Show the steps to compute x13 using 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.


Additional Reading: Read More