0 votes 0 votes Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$ Combinatory kenneth-rosen discrete-mathematics counting recurrence-relation descriptive + – admin asked May 9, 2020 admin 356 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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).$ Mohit Kumar 6 answered May 21, 2020 edited May 21, 2020 by Mohit Kumar 6 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.