search
Log In
0 votes
25 views
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
in Combinatory 25 views

1 Answer

0 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).$


edited by

Related questions

0 votes
2 answers
3
113 views
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
asked May 10 in Combinatory Lakshman Patel RJIT 113 views
...