$T(n) = 2T(n/2) + \Theta(n)$ tight bound

Question

This is the approximated version of average case of quicksort. With the iteration method we end up with $T(n) = n T(1) + n \log n$. We can say that this is easily $O(n \log n)$, but the tight bound is requested. Is $nc + n \log n$ enough to show that it is $\Theta(n \log n)$ too, and how?

Answer 1

A function $f$ is in $\Theta(g)$ if and only if it is both in $\Omega(g)$ and $O(g)$. As you already know, we have $nc + n \log n \in O(n \log n)$, and clearly $nc + n \log n \in \Omega(n \log n)$ as well since $n \log n$ is a lower bound, provided that $c \geq 0$, so we conclude that $nc + n \log n \in \Theta(n \log n)$.