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