Medium Halve Exponent Recursion
In plain English: Compute x raised to the power n efficiently by squaring halves instead of multiplying one at a time.
Squaring the half-result means each call halves n — log(n) multiplications instead of n.
Prompt
Compute x^n in O(log n) time.
Try to write it from scratch before scrolling down.
Solution
def power(x, n):
if n == 0:
return 1
if n < 0:
return 1 / power(x, -n)
half = power(x, n // 2) # halve exponent, square result
if n % 2 == 0:
return half * half
else:
return half * half * x
# Test: power(2, 10) == 1024
# Test: power(2, -2) == 0.25