0

I have worked through most of the quicksort analysis below, but am stuck on how to show that $E[T(n)] \in \Omega(n\cdot\log(n))$ (i.e. part $e.$ in the image below).

I am working off of part $c.$ trying to show, $$ E[T(n)] = \frac{2}{n}\sum_{q=2}^{n-1}E[T(q)] +kn \geq c\cdot n\cdot\log(n)$$ for some $k$ (from $\Theta(n)$ term).

I used substitution (or applied induction hypothesis) but am not sure where to go from here.

$$ E[T(n)] \geq \frac{2}{n}\sum_{q=2}^{n-1}c\cdot q\cdot\log(q) +k\cdot n $$

enter image description here

an4s
  • 3,716
sma
  • 336

1 Answers1

1

If you have

$$E[T[n]]=\Omega \left ( \frac{1}{n} \sum_{q=2}^{n-1} q \log(q) \right )$$

then to get the desired result, it suffices to show that

$$\sum_{q=2}^{n-1} q \log(q)=\Omega(n^2 \log(n)).$$

One way to do this is to treat $\sum_{q=2}^{n-1} q \log(q)$ as a right Riemann sum of $\int_1^{n-1} x \log(x) dx$. Since $x\log(x)$ is an increasing function on $[1,\infty)$, this integral is a lower bound for the sum.

Ian
  • 101,645
  • so something like sum (q log q) >= integral (x log x) = x^2 log (|x|) -(x^2)/4 >= x^2 log (|x|)? How do you show its right to say something like sum (q log q) >= integral? A little confused exactly how you go about this. – sma Mar 14 '18 at 01:47
  • 1
    @skim Write your sum as the right hand rectangle rule of a certain definite integral, it will overestimate the integral because the integrand is increasing. – Ian Mar 14 '18 at 04:03