0

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.

Sivaprakash Prabakaran
  • 1

2 Answers2

0

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.

0

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

Luka
  • 146
  • 7
  • "The number of multiplications is the same as the space complexity" Really? If n = 2: 1 multiplication. If n = 4: 3 multiplications. If n = 8: 7 multiplications. If n = 16: 15 multiplications. Doesn't look much like a log to me. – n. m. could be an AI Jul 21 '22 at 13:15
  • Ah yes your are right – Luka Jul 21 '22 at 15:12