# Tight asymptotic bound for recursive algorithm

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?

• I don't know where you get the sum of $1$ to $n$. I recommend computing a few more values, at least until you get to $T(n) = 5$. To get a rough idea of how $T$ grows, ask yourself this question: if $n$ doubles, how does $T$ change? [P.S. moderator note: I erased the obsolete comments, now the induction case is $T(n/2)+1$.] – Gilles Sep 11 '13 at 11:43
• It's still not clear what is meant by $n/2$. – Yuval Filmus Sep 11 '13 at 13:17
• @YuvalFilmus Only if you assume $n$ to be integer. – G. Bach Sep 11 '13 at 14:34

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