2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$.] $\endgroup$ – Gilles Sep 11 '13 at 11:43
  • $\begingroup$ It's still not clear what is meant by $n/2$. $\endgroup$ – Yuval Filmus Sep 11 '13 at 13:17
  • $\begingroup$ @YuvalFilmus Only if you assume $n$ to be integer. $\endgroup$ – G. Bach Sep 11 '13 at 14:34
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.