In Python

State g(n)'s runtime complexity:

def f(n): if n <= 1:` return 1 return 1 + f(n/2) def g(n): i = 1 while i < n: f(i) i *= 2