I have the following code for calculating x^n:

def power(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x

    d = n//2
   
    return power(x, d) * power(x, n-d)

I want to determine the space and time complexity for this code.

time complexity: (my analysis)

1. At each level x the function calls itself 2^x times.
2. Since we are dividing n by 2 at each level, there will be logn levels (logn 1 in case n is odd) (log is of base 2)
3. So, total number of function calls will be 2^0 2^1 2^2 ... 2^logn.
4. Each function call will do some k constant work.

I don't know how to simplify this to determine big O.

space complexity: (my analysis)

1. At max, there will be logn 1(in case of odd n) function calls in stack at a given time.
2. So, space complexity will be O(logn).

Need help in determining the time complexity and verifying space complexity.

CodePudding user response：

Let P(n) the number of multiplies involved in the call Power(x, n).

For n a power of 2, let 2^m, we have the simple recurrence P(2^m) = 2 P(2^(m-1)) with P(2) = 1.

Hence the solution P(2^m) = 2^(m-1) or P(n) = n/2.

CodePudding user response：

The number of multiplications is the same as the space complexity in O(log n), but a multiplication itself is not in O(n') or O(1) (as long as number bit-sizes are not limited by a constant), for n' being the integer bit-size. The school-method for example is of $O(n'^2)$ --> https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

The algorithm you are mentioning is kind of the Exponentiation by squaring, here you can find more detailed answers about the running time: https://en.wikipedia.org/wiki/Exponentiation_by_squaring