Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Tight asymptotic bound for recursive algorithm

, ,
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?

#### 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