Złożoność algorytmu Heapsort - algorytm

W książce jest napisane:

Najgorszy czas działania heapsortu to (nlgn). Jest to jasne, ponieważ sortowanie ma dolną granicę (nlgn)

Ale czy ktoś może mi pomóc i pokazać mi wyraźnie, że dolna granica tej funkcji jest równa Omegi (nlgn)?

Odpowiedzi:

Wygląda na to, że książka opiera się na fakcieże heaport jest algorytmem porównywania opartym na porównaniu w tym stwierdzeniu. Tak więc automatycznie pokazano, że ten paradygmat algorytmów sortowania ma niższą granicę Omegi (nlgn):

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list