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

#1 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 203
  • View blog
  • Posts: 1,730
  • 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  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • 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).
Was This Post Helpful? 0
  • +
  • -

#3 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 203
  • View blog
  • Posts: 1,730
  • 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.
You can learn more here:
http://cns2.uni.edu/...6/solution.html
Was This Post Helpful? 0
  • +
  • -

#4 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12134
  • View blog
  • Posts: 45,114
  • Joined: 27-December 08

Re: Sorting question

Posted 10 February 2012 - 06:28 AM

Moved to Computer Science.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2499
  • View blog
  • Posts: 3,952
  • Joined: 21-June 11

Re: Sorting question

Posted 10 February 2012 - 07:04 AM

View Postblackcompe, 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).
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1