Recursive equation

Question

I am trying to solve $T(n)=2T(\frac{n}{2}) +1 $ where $T(1) = \theta(1) $,since we have iterator $n->\frac{n}{2}$ then the height of the tree is $lg(n)$ but why $T(n)=1+2+4+8+ ..+n$ ,how do I deduce that the last term is exactly n and the number of terms is $lg(n)+1$ shouldn't it be just $lg(n)$

Let $T(n)=S(n)-1.$ Then your recursion will be $S(n)=2S\left(\frac n2\right).$ Do you define $T(n)$ on the numbers of form $2^kc$ only? — Minz, May 09 '17 at 06:24

score 0 · Accepted Answer · answered May 09 '17 at 06:23

\begin{align} T(n) &= 2T(n/2) + 1 \\ T(n) &= 4T(n/4) + 2 + 1 \\ T(n) &= 8T(n/8) + 4 + 2 + 1 \\ T(n) &= 16T(n/16) + 8 + 4 + 2 + 1 \\ \vdots\\ T(n) &= 2^rT(n/2^r) + \sum_{k=0}^{r-1}2^k\\ T(n) &= 2^rT(n/2^r) + 2^r-1\\ T(n) &= 2^r(T(n/2^r) + 1) - 1\\ \end{align}

And since $T(1) = \theta(1)$, we have $n/2^r = 1$ when $n = 2^r$ or when $r = \lg(n)$, meaning:

$$T(n) = 2^{\lg(n)}(\theta(1) + 1) - 1 = n(\theta(1) + 1) - 1$$

Recursive equation

1 Answers1