# Fast Exponentiation

Let's try a couple of more problems before moving on to the time & space complexity part properly. Will learn about how to calculate **pow(x, n) **in an efficient way in this article, and will solve 1 more in the next article.

We'll do some informal thinking about the time complexity in this article as well.

## Pow(x, n)

Come on, go on to the ** Solve** link and try it yourself first. The crux is that given a double value

*x*and an integer

*n*, we need to return the value of x

^{n }

### Iterative Approach

A very straight forward iterative solution could be as follows:

## Implementation (iterative)

```
double myPowHelper(double x, int n) {
double ans = 1.0;
for(int i = 0; i < n; ++i)
ans *= x;
return ans;
}
double myPow(double x, int n) {
if(n >= 0)
return myPowHelper(x, n);
return 1.0/myPowHelper(x, abs(n));
}
```

## Time & Space Complexity

Time: O(N)

Space: O(1)

### A similar Recursive Approach

There could be a recursive approach as well, similar to the iterative approach above.

Of course, 1 thing to cover is that if n is non-negative, then simply calculate *pow(x, n)*, otherwise calculate *pow(x, abs(n))* and return *1.0/pow(x, abs(n))*.

```
double myPow(double x, int n) {
if(n >= 0)
return myPowHelper(x, n);
return 1.0/myPowHelper(x, abs(n));
}
```

Now, the *myPowHelper() *function can be implemented based on this observation that given a x and n value, if we already have the answer for *myPowHelper*(x, n - 1), then finding the answer to the actual problem i.e. *myPowHelper(x, n)* is not very hard, because:

x^{n} = x^{n-1} * x

The *myPowHelper() *can be implemented using recursion as follows:

## Implementation 1 (recursive)

```
double myPowHelper(double x, int n) {
if(!n)
return 1.0;
return myPowHelper(x, n - 1) * x;
}
```

Now, if we try to analyse its time complexity from the 1st principles, when calling *myPowHelper(x, n)*, it'll make a recursive call to *myPowHelper(x, n - 1)*, which in turn will make a recursive call to *myPowHelper(x, n - 2)* and so on, until we reach *myPowHelper(x, 0)*.

After that, *myPowHelper(x, 0)* will simply return 1 to *myPowHelper(x, 1)*, and then *myPowHelper(x, 1)* will simply return x to *myPowHelper(x, 2)*, and so on until it wraps up all the way to *myPowHelper(x, n)* and *myPowHelper(x, n)* returns x^{n} to the *myPow()* function.

That means, approximately *n *recursive calls are made in total, and in each recursive call, if we look at the code, the work done takes O(1) time i.e. just making a function call and getting it over with.

Some of you may get an idea that the time complexity should be O(N), others may not. If you fall into the others category, hold tight, we'll make it clear in a much better way in the coming articles.

## Time & Space Complexity

Time: O(N)

Space: O(N) (because of the call stack, will explain more clearly in the coming articles)

### A better Recursive Approach

Here, what we'll try to do is, that instead of breaking down the problem of *myPowHelper(x, n)* to *myPowHelper(x, n-1), *we'll try to break it into an even smaller problem, so that eventually it takes us less number of steps to reach the base case i.e. *myPowHelper(x, 0).*

The observation here is that *x ^{n }*can also be found using x

^{n/2}

#### Example 1 ( n is even)

Let's say n = 8, I think it'll be easy to understand that x^{8} can be easily found if we get the value of x^{4}:

x^{8} = (x^{4})^{2}

If we call x^{4} as partial answer, then x^{8} = *partial_ans*^{2}

#### Example 2 ( n is odd)

Let's say n = 11, I think it'll not be very hard to understand that x^{11} can be found if we get the value of x^{5} (because if integer division is done, then 11/2 = 5):

x^{11} = (x^{5})^{2} * x

If we call x^{5} as partial answer, then x^{11} = (*partial_ans)*^{2} * x

Following the above examples, try to code it yourself before looking at the solution below:

## Implementation 2 (recursive)

```
double myPowHelper(double x, int n) {
if(!n)
return 1.0;
double partialAns = myPowHelper(x, n/2);
// Squaring the partialAns
partialAns *= partialAns;
return n % 2? partialAns * x : partialAns;
}
```

Now here, I'm not going to attach a diagram xD, but you can try to imagine yourself that the recursive calls will go like:

*myPowHelper(x, n) -> myPowHelper(x, n/2) -> myPowHelper(x, n/4) ..... -> myPowHelper(x, 1) -> myPowHelper(x, 0)*

As opposed to the inefficient approach, this will lead to just O(LogN) recursive calls, leading to a much better time complexity.

## Time & Space Complexity

Time: O(LogN)

Space: O(LogN)

Just to let you know, this is an important problem that'll come handy in a few other concepts as well, so absorb it completely.