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

1

First a remark on notation - in analysis of algorithms, $\Omega (f(n)), \Theta (f(n)),$ et. all are not functions but rather sets. This is discussed adequately in a good book (such as CLRS) and summarized here.

The OP's statement in the post title is incorrect. If $f(n)$ is the runtime of heapify (known to be $\Theta (\lg n)$ ), then there exist positive constants $k_1, k_2 $ such that $k_1 \lg n \le f(n) \le k_2 \lg n$ for $n$ sufficiently large. For $n$ sufficiently large, we have $k_2 \lg n < n\lg n$ (just take $n> k_2$), so that the assertion that heapify is $\Omega (n\lg n)$ is false. You are probably thinking of heapsort, whose worst case is $O (n\lg n).$ For practical purposes, lower bounds on worst case performance are meaningless (as they might be trivial) unless accompanied by an asymptotically similar upper bound (hence the utility of the $\Theta $ notation.) Hope this helps.