Complexity Analysis
def power(base, exp):
if exp == 0:
return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half
return base * power(base, exp - 1)What is the time and space complexity?
Work it out before scrolling down.
Time
O(log n)
Space
O(log n)
How to derive it
Each recursive call either halves exp (even case) or subtracts 1 then halves (odd → even → halve). At most 2 × log₂(n) calls before reaching 0. Each call does O(1) work. Recursion depth is O(log n) → O(log n) stack space. This is fast exponentiation — O(log n) vs naive O(n).