Tight asymptotic bound for recursive algorithm I have this algorithm where:

$$
T(n) =
\begin{cases}
  1 &amp; \text{if}\; n \le 1 \\
  T(n/2) + 1 &amp; \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?
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$.