Basic recurrence problem, not sure if solution is correct (solution included)

Question

I have the following exercise:

We know that the solution of $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \log_2 n)$. Show that the solution of this recurrence is also $\mathcal{\Omega}(n \log_2 n)$. Conclude that the solution is $\mathcal{\Theta}(n \log_2 n)$.

To solve this i used the substitution method with induction and got the following solution:

$T(n) \ge 2\left(\dfrac{cn}{2}\right) \log_2 \left(\dfrac{n}{2}\right) + n$
$= cn \log_2\left(\dfrac{n}{2}\right) + n$
$= cn \log_2 n - cn \log_2 2 + n$
$= cn \log_2 n - cn + n$
which is larger than or equal to $cn \log_2 n$

for $c = 1$, we get equality.

If the same solution is valid for both the upper and lower bounds, that means that is valid for $\mathcal{\Theta}$, correct?

If my solution is wrong, please do elaborate.

Thank you for taking the time to help.

Answer 1

You're okay until you say in the eighth line

which is larger than or equal to $cn\log_2n$

To be precise, you should note that $$ cn\log_2n-cn+n\ge cn\log_2n $$ if and only if $-cn+n\ge 0$, which is satisfied iff $c\le 1$. You correctly note that you do indeed have equality if $c=1$, but there are other values of $c$ which also satisfy the above inequality. Two lines later you're right to say that if the same solution (namely $c=1$) holds for upper and lower bounds then $T(n)=\Theta(n\log_2 n)$, but there's nothing that requires the $c$ values for the upper bound and the lower bound be the same.

One other point: your induction proof is missing a base case. If $T(1) =0$ then you'll indeed have $T(n)\ge n\log_2 n$ for all $n\ge 1$. Otherwise, you'll have $T(n)=nT(1)+n\log_2 n$. This is still $\Theta(n\log_2n)$, but I'd have docked you a point or two for not taking care of the base case.