# Sorting question

Page 1 of 1

## 5 Replies - 1735 Views - Last Post: 10 February 2012 - 07:04 AM

### #1 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,731
• Joined: 13-March 10

# Sorting question

Posted 09 February 2012 - 09:02 PM

I have the following question to solve:

Prove worst-case lower bound (counting comparisons) for sorting 5 elements.

I have already answered it but i dont know whether i did it correctly. Basically, what i did is, i have proved that ANY comparison-based algorithm will have lower bound Omega(nlgn). HOWEVER, i have not taken into account the 5 elements that appear in the question since i have no idea how that fits.

So, my question is: by proving that any comparison-based algorithm has worst case lower bound Omega(nlgn) do i answer this question?

This post has been edited by darek9576: 09 February 2012 - 09:26 PM

Is This A Good Question/Topic? 0

## Replies To: Sorting question

### #2 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Sorting question

Posted 09 February 2012 - 10:33 PM

So that's basically asking what's the best you can do with the worst case input? Am I correct in saying that? If I'm not mistaken sorting 5 elements in reversed sorted order with quicksort is O(n2). Slower sorts, like insertion sort, are definitely O(n2). Insertion sort would be an easy one to prove informally: The inner loop does a O(n) shift operation for every outer loop operation, where the outer loop is O(n).

### #3 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,731
• Joined: 13-March 10

## Re: Sorting question

Posted 09 February 2012 - 10:44 PM

Not really. I dont understand the question as well but about your answers i can tell you that im currently studying comparison-based sorting algorithms and it can be done in 7 comparisons using a decision tree.
http://cns2.uni.edu/...6/solution.html

### #4 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

## Re: Sorting question

Posted 09 February 2012 - 10:48 PM

Quote

i can tell you that im currently studying comparison-based sorting algorithms and it can be done in 7 comparisons using a decision tree.

Then your talking best case scenario, right? "Can be" doesn't mean "always will be." You said:

Quote

Prove worst-case lower bound

Eh, I'm not sure. Good luck with that.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

## Re: Sorting question

Posted 10 February 2012 - 06:28 AM

Moved to Computer Science.

### #6 sepp2k

• D.I.C Lover

Reputation: 2549
• Posts: 4,069
• Joined: 21-June 11

## Re: Sorting question

Posted 10 February 2012 - 07:04 AM

blackcompe, on 10 February 2012 - 06:48 AM, said:

Quote

i can tell you that im currently studying comparison-based sorting algorithms and it can be done in 7 comparisons using a decision tree.

Then your talking best case scenario, right?

No, he's talking any possible scenario using the best possible algorithm. Of course if you use another algorithm, you can end up with worse running times, but if we use that reasoning, there is no worst case runtime because you can always come up with an algorithm that takes even longer.

Quote

So, my question is: by proving that any comparison-based algorithm has worst case lower bound Omega(nlgn) do i answer this question?

No. The question isn't about big-Oh, it's about an actual number. You already know that it can be done in 7 steps, so now you need to show that it can't be done in less.

PS: If the question was about big-Oh, it would be O(1) though because the runtime will always be O(1) if the size of the input is constant. In this case you know that the algorithm will never use more than 7 comparisons, so clearly it's in O(1) because when you have an upper bound that is a constant, that means it's in O(1).