Power of X (Pow(x, n))

Difficulty: Medium

Problem

Write a function that computes x raised to the integer power n, without using a built-in power function. It has to work when n is negative too. Solve it using recursion.

Example

Input: x = 3.0, n = 4
Output: 81.0
Explanation: 3^4 = 3 × 3 × 3 × 3 = 81.0

Brute-force approach

The plain way is a loop: start with result = 1 and multiply by x, n times (for a negative n, loop |n| times and take 1 / result). It is n multiplications with O(1) space, which is the problem the recursion avoids, and also the O(1)-space alternative to the O(log n) pile of calls.

Steps

  1. Set result = 1
  2. Repeat n times: result = result * x
  3. If n was negative, return 1 / result instead

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • n multiplications: about a billion for n = 1,000,000,000
  • Too slow for large n

Optimal approach

Key insight: If someone magically gives you x^(n/2), then x^n = (x^(n/2))². Trust the recursion, square the result!

Use the Leap of Faith recipe to build a recursive fast power solution. Trust that myPow(x, n/2) works, then square the result.

Steps

  1. Base case: if n == 0, return 1
  2. If n < 0, return 1 / myPow(x, -n)
  3. If n is even: half = myPow(x, n // 2), return half × half
  4. If n is odd: return x × myPow(x, n-1)

Time complexity: O(log n) · Space complexity: O(log n)

Pseudocode

function myPow(x, n):
    if n == 0: return 1
    if n < 0: return 1 / myPow(x, -n)
    if n is even:
        half = myPow(x, n // 2)   // whole-number division: n // 2 in Python
        return half * half
    else:
        return x * myPow(x, n - 1)

Hints

  • What's the simplest power to compute? (Base case: n = 0)
  • If someone gives you x^(n/2), can you get x^n? (Leap of Faith!)
  • Handle odd n by reducing it: x^n = x × x^(n-1)
  • An even n splits into two equal groups of n / 2, so ONE call on n // 2 is enough. Keep the answer in half and square it; never call myPow twice. (In Python use n // 2, whole-number division, so the exponent stays an integer.)
  • For an odd n, spend one extra x: n - 1 is even, so the halving works on the next call.

Complexity questions

What is the time complexity of recursive fast power?

O(log n). We halve the exponent at each step, giving log₂(n) levels of recursion, O(log n) total multiplications. Exactly: floor(log₂ n) halvings plus one extra multiplication for each 1 in n's binary form, at most 2 * floor(log₂ n) + 1 multiplications (5 for n = 10).

What is the space complexity of the recursive fast power approach?

O(log n). The recursion depth is O(log n), and each frame uses constant space, O(log n) total.

How many recursive calls does myPow(2, 10) make?

6. myPow(2,10) → myPow(2,5) → myPow(2,4) → myPow(2,2) → myPow(2,1) → myPow(2,0). That's 6 calls total (including the base case). Much better than 10!

Check your understanding of Power of X (Pow(x, n))

If someone magically gives you 2^5 = 32, how do you compute 2^10?

32 × 32 = 1024 (square it!). That's the Leap of Faith! If you TRUST that myPow(2, 5) = 32, then myPow(2, 10) = 32 × 32 = 1024. Just square the result!

How do we handle negative exponents like x^(-3)?

Return 1/(x^3). x^(-n) = 1/(x^n). So 2^(-3) = 1/(2^3) = 1/8 = 0.125. We convert it to a positive exponent problem first.

Why is this approach O(log n) instead of O(n)?

We halve the exponent at each step. Each recursive call halves the exponent (for even n). So there are about log₂(n) halvings (an odd n adds one extra call each time). For n=1,000,000,000 that's only about 30 halvings!

Related problems

Keep practising