# Interview Questions

# Compute x^n (x to the power n)

- September 25, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

Write a C function to compute x^{n} which uses minimum number of multiplications.

unsigned int power(double x, unsigned int n)

**Brute Force Solution: O(n) time**

The brute force method for this is to use a for loop

double power(double x, unsigned int n) { double product = 1; for(int i=0; i<n; i++) { product = product * x; } return product; }

We can also write the function recursively. But recursion gives no advantage in terms of performance. In fact it is always less optimal than non-recursive version.

double power(double x, unsigned int n) { if (n == 0) return 1; return x * power(x, n-1); }

**Time Complexity:** O(n)

**Space Complexity:** For non-recursive version its O(1), for recursive version its O(n).

**Optimized Solution: O(lg(n)) time**

A Better Solution is to do Exponentiation by squaring. In this method we take advantage of the basic formula:

x^{n+m} = x^{m} * x^{n}

Hence,

x^{n} = x^{n/2} * x^{n/2 } (If x is even)

x^{n} = x * x^{n/2} * x^{n/2} (If x is odd)

double power(double x, unsigned int n) { if( n == 0) return 1; double retValue = 1; while(n) { if(n%2) retValue = retValue * x; x = x * x; n = n/2; } return retValue; }

The recursive version of above code will be something like:

double power(double x, unsigned int n) { if( n == 0) return 1; double temp = power(x, n/2); if (n%2 == 0) return temp*temp; else return x*temp*temp; }

*Note that the above code is not same as the below code* (though both are recursive and both does exponential multiplication)

unsigned int power(double x, unsigned int n) { if (n == 0) return 1; if(x%2 == 0) return power(x, n/2) * power(x, n/2); else return x * power(x, n/2) * power(x, n/2); }

In the above code we are calling power method twice and hence it will be much more time consuming. (if n=10) then power(x,5) will be called twice. Its a typical problem with recursion.

The approach in the first recursive function is that call power(x,5) once and store its value in a variable (temp) and for second time use that value. This approach is called Dynamic Programming.

You can learn more about Dynamic Programming here, here or here…

The changes are rare for submitting news in people. Your blog is really nice for me and also i have followed your post for getting great news online. The clear and understandable sources are applicable for all. The wedding photos and some of engagement plans are available to say for all customers in online. You can discuss your queries in custom essay writing service. In this website is given marvelous information and some of peaceful study for all.