Cheap and Secure Web Hosting Provider : See Now

[Solved]: Tight asymptotic bound for recursive algorithm

, , No Comments
Problem Detail: 

I have this algorithm where:

$$ T(n) = \begin{cases} 1 & \text{if}\; n \le 1 \\ T(n/2) + 1 & \text{otherwise} \\ \end{cases} $$

So, evaluating for $T(0), T(1), T(2), T(3), \ldots, T(n)$, I'm getting values like: $$ 1, 1, 2, 2, 3, 3, \ldots, n, n $$

I assume this is twice the sum of $1$ to $n$, that would be the same as $n (n+1)$ or $n^2+2$.

Is my assumption ok?

Asked By : diegoaguilar

Answered By : Yuval Filmus

Suppose that $n = 2^k$. Then $$ T(n) = T(2^k) = T(2^{k-1}) + 1 = T(2^{k-2}) + 2 = \cdots = T(2^0) + k = k + 1. $$ So $T(n) = \log_2 n + 1$ in that case. In the general case you would get something similar, $T(n) = \lfloor \log_2 n + 1\rfloor$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14264

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback