def f(n): i = 1 while i < n: i *= 2 print(i) 2: c_1 3, 4, 5: c_2 Line 2: run 1 time Lines 3, 4, 5: Run lg(n) times, since i doubles each time. c_1 + c_2 lg(n) Theta( log(n) )