1
$\begingroup$

Worst case of Heapify is $\Omega(n \lg n)$

I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent.

Thanks.

  • 0
    Is your question simply whether $\Theta(n\lg n)$ is equivalent to $\Theta(\lg n)$?2012-06-22
  • 2
    Notice that if you write n lg n in $\TeX$ it looks like $n lg n$, but if you write n \lg n, you get $n\lg n$. So the backslash has at least two effects: it prevents "lg" from being italicized, and it results in proper spacing before and after it. It's standard usage, like \ln and \log and \sin and \max, and \det etc. I think it might no work in plain $\TeX$ without using some standard packages, but it works here. I edited the question accordingly.2012-06-22
  • 0
    Thanks, I don't knew that.2012-06-23

1 Answers 1