# Interview Questions

# Divide & Conquer Approach to find a^n

- June 13, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

If you want to compute a^n ( a raised to the power n), then the algorithm is simple:

long power(int a, int n) { long prod = 1, i=0; for(; i<n; i++) prod = prod * a; return prod; }

But the above function will take O(n) time.

Write a divide & conquer algorithm which takes O(lg(n)) time to compute **a ^{n}**.

### Solution:

**Linear Approach (given in question):**

The function given in question will take O(n), because the product will happen n times.

The result is derived in a linear fashion multiplying a, n times. So Product is computed as

Prod = a * a * a * … … n-times

By the way, for those who are fascinated with recursion, the corresponding recursive function (for linear approach is)

long power(int a, int n) { if(n==0) return 1; else return a * power(a, n-1) }

**Divide & Conquer Approach:**

If we use the divide & conquer approach the time complexity can be reduced to O(lg(n)). This way we can get the same difference which is there in the linear search and binary search.

The Divide & Conquer approach square a each time, rather than multiplying it with a itself. i.e If we want to compute 2^8 we actually compute it like

Prod = ( (a ^ 2) ^ 2) ^ 2

Hence the operation (of square) will be performed only 3 (lg(8)) times and not 8 times.

I am sure you can write the program on your own, to help you I am writing the recursive program of divide-n-conquer below, If you are not able to write the iterative version, just leave a comment or mail me at kamal@ritambhara.com

/** divide & Conquer function to compute a^n. * n is a positive integer */ long power(int a, int n) { if(n==0) return 0; // putting a check to avoid unnecessary recursive calls if(a == 0) return 0; if(n%2 == 0) // b is even return power(a*a, b/2); else return a * power(a*a, b/2); }

**Note:** Recursion is not really a good optimized practice. Because each recursive call will have an overhead of function call and will take extra memory (to store the activation record of a function) on the stack.

1 more error. You need to put an exit condition. I put n=n/2 in my code and used the condition while (n>1), so that once value of n becomes less than 1. The recursion stops.

Thanks.This post was really helpful. Especially the divide and conquer approach.

I would like to point out one error in the divide and conquer code.

I believe it should be-

if (n==0)

return 1;