0

My proof that $T(n) = 2T(n/2) + n$ is $\Omega(n \lg n)$:

Assume $T(m) \geq cm \lg m$ for $m < n$.

$T(n) \geq cn \lg(n/2) + n = cn \lg n - cn + n \geq cn \lg n$, for $0 < c \leq 1$.

Since we just have to find there exists a positive constant c, are we done?

Community
  • 1
Dak Song
  • 151
  • It seems like you're trying to do an induction, but where is your base case? – Peter Huxford Aug 07 '16 at 08:51
  • 1
    As usual in such situations, the rigorous setting lurking behind the question is that one studies sequences $t_k=T(2^k)$ such that $t_k=2t_{k-1}+2^k$ for every $k$. It happens that this recursion can be solved exactly, by $t_k=k2^k+t_02^k$, hence $t_k=\Theta(k2^k)$ and, along the subsequence of the powers of $2$, $T(n)=\Theta(n\lg n)$ (which is more than the desired conclusion). – Did Aug 07 '16 at 10:00
  • 1
    With the caveat of the previous comment in mind, note that the proof presented in the question works: just choose $c$ positive and small enough such that the base case $T(n)\geqslant cn\lg n$ holds. – Did Aug 07 '16 at 10:01
  • 1
    "which is more than the desired conclusion": Please read: which is less and more than the desired conclusion, less because one is restricted to the powers of $2$ and more because one gets $\Theta$ asymptotics instead of $\Omega$ asymptotics. – Did Aug 07 '16 at 10:50

0 Answers0