Kenneth Rosen Edition 7 Exercise 8.3 Question 10 (Page No. 535)

Question

Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$

Answer 1

Use Master Theorem with  $ a = 1, b = 2, c = 1, d = 0.$

Since $ a = b^{ d} ,(d=log_{a}b)$

we know that f(n) is   $ O(n^{ d} log n) = O(log n).$