How to prove worst-case number of inversions in a heap is O(nlogn)?
- by Jacques
I am busy preparing for exams, just doing some old exam papers. The question below is the only one I can't seem to do (I don't really know where to start). Any help would be appreciated greatly.
Use the O(nlogn) comparison sort bound, the theta(n) bound for bottom-up heap construction, and the order complexity if insertion sort to show that the worst-case number of inversions in a heap is O(nlogn).