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) Solve

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ⁿ

Iterative Approach

A very straight forward iterative solution could be as follows:

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));
}

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ⁿ = x^n-1 * x

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

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ⁿ 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.

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ⁿ can also be found using x^n/2

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

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.

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.