1

Currently studying "Introduction to Algorithms" , currently stuck at trying to verify an upper bound to a recurrence via substitution when I already know for sure from another method that it is correct.

For $T(n) = T(n/2) + n$, I know from summating the cost at each level on the recurrence tree that it forms a geometric progression, so in the end, the upper bound is $\cal O(n)$.

However, when I substitute $T(n) = cn$, $c$ is some constant into the recurrence, I end up getting $T(n) \leqslant cn + n - c$ which doesn't conclusively show that $\cal O(n)$ is the upper bound for $T(n)$, even though i know for a fact, by the proof above and from googling that it is $\cal O(n)$.

Hence my question is why doesn't the verification using substitution work? Am I doing something wrong? Or is there some way to proceed from my dead end that leads me to conclude $T(n) = \cal O(n)$?

emacs drives me nuts
  • 10,390
  • 2
  • 12
  • 31
tiberius99
  • 23
  • 1
    It is $O(n)$. Note that $T(2^n)=T(1)+2^{n+1}-2$. Assuming continuity, we have $T(n)=T(1)+2n-2$. – Rushabh Mehta Feb 17 '20 at 04:10
  • 1
    Also, what are you plugging in? If we substitute $T(n)=an+b$, we get $$an+b=a\cdot\frac n2+b+n=\left(\frac a2+1\right)n+b$$So, $a=\frac a2+1$, so $a=2$, and $b$ depends on $T(1)$. – Rushabh Mehta Feb 17 '20 at 04:12
  • but why dosent this logic in substitution work for T(n) = 2T(n/2) + n ? i know from the recursion tree that T(n) = O(nlogn), yet if were to try (asssuming T(n) = O(n)), substituting T(n) = an + b into T(n), wouldnt i get an + b + n = (a+ 1) + b , and conclude a= a + 1 and that T(n) = O(n) ? – tiberius99 Feb 18 '20 at 04:49
  • i know somewhere in that logic i am wrong, as i have no problem understanding the actual bounds from the recursion tree, i'm just really confused in the use of substitution to verify the bound, and what is the difference between the logic of concluding the bound from substitution for the above 2 scenarios T(n) = 2T(n/2) + n VS T(n) = T(n/2) + n @DonThousand – tiberius99 Feb 18 '20 at 04:52

1 Answers1

0

Let $n=2^k$, $k=0,1,2,\ldots$ and assume $T(1)=1$. Then \begin{align} T(2^0)&=1\\ T(2^1)&= T(2^0) + 2^1 = 1 + 2 = 3\\ T(2^2)&= T(2^1) + 2^2 = 3 + 2^2 = 7\\ T(2^3)&= T(2^2) + 2^3 = 7 + 8 = 15\\ &\ \ \vdots\\ T(2^k) &= 2^{k+1}-1, \end{align} hence $T(n) = 2n-1$, so that $T(n)\in\Theta(n)$.

Math1000
  • 36,983