Complexity Analysis
def powers_of_two(n):
result = []
x = 1
while x < n:
result.append(x)
x *= 2
return resultWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(log n)
Space
O(log n)
How to derive it
x doubles each iteration: 1, 2, 4, 8, ..., 2^k. Stops when 2^k ≥ n, so k = log₂(n) iterations. The result list stores log₂(n) elements. Both time and space are O(log n).