All geek questions in one place

How to prove the worst number of inversions in the Q (nlogn) heap?

I'm busy preparing for exams, just doing some old exam papers. The question below is the only one that I cannot do (I do not know where to start). Any help would be greatly appreciated.

Use the comparison sorting binding Ω (nlogn), theta (n) associated with constructing the heap from the bottom up, and the complexity of the insertion sort order to show that the worst number of inversions in the heap is Q (nlogn).

+3
source share
1 answer

The complexity of sorting an insert is O (n + d), where d is the number of inversion pairs.

, , heapify (Theta (n)), . ?

+2

Source: https://habr.com/ru/post/1749230/

More articles:


All Articles