How to prove worst-case number of inversions in a heap is Ω(nlogn)?

tags:

views:

93

answers:

2

+2 Q:

How to prove worst-case number of inversions in a heap is Ω(nlogn)?

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 Ω(nlogn) comparison sort bound, the theta(n) bound for bottom-up heap construction, and the order complexity of insertion sort to show that the worst-case number of inversions in a heap is Ω(nlogn).

+2 A:

The complexity of insertion sort is O(n+d) where d is the number of inversion pairs.

Now say you had a set of numbers, which you heapify (Theta(n)) and then perform insertion sort on them. What does it say about the worst case number of inversion pairs in the heap array?

Moron 2010-06-09 16:40:34

I think that's the question: what DOES it say? :)

IVlad 2010-06-09 18:01:48

@|Vlad: Do I really need to spell it out? The smiley makes me think you are joking, but no upvote makes me think you are serious ;-) :-P

Moron 2010-06-09 18:07:27

@Moron - personally I figured it out, but I think more details would be nice for the OP. Like what `Omega` and `Theta` mean and how they help you get to the result.

IVlad 2010-06-09 18:57:20

@IVlad: I presume OP understands what the terms mean as he is preparing for an exam and this is one of the questions in the previous exam! I intentionally left it unfinished as I treated this like 'almost homework'. If OP comes back asking for clarification, I will provide them, but not until they have put in some effort themselves.

Moron 2010-06-09 19:06:39

@Moron - fair enough :). +1

IVlad 2010-06-09 19:10:00

Im going through some other papers now. But I do know what they mean. Thanks, I think I got it now, but will write it out later to be sure. :)

Jacques 2010-06-09 20:02:35

A:

would be interested in seeing the answer to this

Buttersnaps 2010-06-12 19:50:15

ansaurus

tags:

views:

answers:

How to prove worst-case number of inversions in a heap is Ω(nlogn)?

related questions