Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is your question simply whether $\Theta(n\lg n)$ is equivalent to $\Theta(\lg n)$? –  Michael Hardy Jun 22 '12 at 1:35
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. –  Michael Hardy Jun 22 '12 at 1:37
    
Thanks, I don't knew that. –  Albert Jun 23 '12 at 1:42

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.