Tight asymptotic bound for recursive algorithm

Question

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?

• Gilles 'SO- stop being evil': 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$.]
• Yuval Filmus: It's still not clear what is meant by $n/2$.
• G. Bach: @YuvalFilmus Only if you assume $n$ to be integer.

Answer 1

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