0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Check the definition of limit and $n < nlogn$ for $n \geq 2$. $\endgroup$
    – Functor
    Commented Mar 10 at 0:51

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .