My Math Forum Lower and upper bounds

 Computer Science Computer Science Forum

 April 3rd, 2013, 09:09 AM #1 Newbie   Joined: Apr 2013 Posts: 6 Thanks: 0 Lower and upper bounds I am thinking lower and upper bounds for sorting. I used different objects ( pencils and so on ) to do this. If I have five keys, lower bound is 7, but upper bound is 9? and if I have six keys, lower bound is 10, but upper bound is 11? Lower bounds must be correct, but what about upper bounds?
 April 3rd, 2013, 07:16 PM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Lower and upper bounds What precisely are you asking for lower and upper bounds on?
 April 3rd, 2013, 09:13 PM #3 Newbie   Joined: Apr 2013 Posts: 6 Thanks: 0 Re: Lower and upper bounds Lower and upper bounds for number of comparisons. And all keys are unequal.
April 4th, 2013, 08:10 AM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Lower and upper bounds

Quote:
 Originally Posted by will_hunting_math Lower and upper bounds for number of comparisons. And all keys are unequal.
Number of comparisons for what sorting algorithm?

 April 4th, 2013, 11:22 AM #5 Newbie   Joined: Apr 2013 Posts: 6 Thanks: 0 Re: Lower and upper bounds I just mean: lower and upper bound for number of comparisons, and keys are unequal. So, no sorting algorithm. But we can use decision tree here.
 April 4th, 2013, 01:57 PM #6 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Lower and upper bounds No sorting algorithm, OK. But what are you trying to do? If you're not doing anything a lower bound on the number of comparisons is 0. If you are doing something, tell me what!
 April 4th, 2013, 02:10 PM #7 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Lower and upper bounds If you had asked only about lower bounds and given your examples I would have thought you were asking: what is the smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects in the worst case? But you also ask about upper bounds and so I don't know what to conclude.
 April 4th, 2013, 09:35 PM #8 Newbie   Joined: Apr 2013 Posts: 6 Thanks: 0 Re: Lower and upper bounds I am sorry. I meant that not any specific sorting algorithm. These are difficult things and to me these are hard to explain. So, First example: n=5. Other example: n=6. And, indeed, what is the smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects? And now, if n=5, that lower bound is only 7, that must be best way to sort five keys/elements. But upper bound, that means in the worst case, so how many comparisons is needed at most. I just draw some pictures and got that comparisons are at most ( upper bound ) 9. And if n=6, smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects must be 10. And upper bound is...I believe 11. But ah... I see. Upper bound and lower bound can at least sometimes be same? If n=3, then lower bound is 3, and also upper bound is 3. Maybe now my question is clearer.
April 5th, 2013, 06:35 AM   #9
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Lower and upper bounds

Quote:
 Originally Posted by will_hunting_math And if n=6, smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects must be 10. And upper bound is...I believe 11. But ah... I see. Upper bound and lower bound can at least sometimes be same? If n=3, then lower bound is 3, and also upper bound is 3. Maybe now my question is clearer.
Not clear, sorry. The smallest number of comparisons to sort 6 objects is 0. The smallest number of comparisons to sort 6 objects and prove that the sorting is correct is 5 ("best case"). The smallest number of comparisons needed to sort 6 objects in the worst case is 10. So what is 11?

 April 5th, 2013, 10:10 AM #10 Newbie   Joined: Apr 2013 Posts: 6 Thanks: 0 Re: Lower and upper bounds Sorry again. All right. I guess I don't quite understand how to think this problem. Maybe what you said: " what is the smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects in the worst case? " is exactly what I'm chasing. And I saw my friend today, and he told me that Donald Knuth has showed that: if n=5 and then the smallest number of comparisons any comparison-based sorting algorithm can use to sort n unequal objects in the worst case is 7. Like this, my friend said that this is a "method" I'm chasing, but he can't say more, said that this is a difficult problem.

 Tags bounds, lower, upper

,

,

what are lower and upper bounds in math

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post p99410 Algebra 2 December 17th, 2013 03:08 PM adamj6100 Algebra 1 October 23rd, 2010 11:15 AM Shaitan00 Applied Math 10 September 21st, 2008 09:09 AM Kiranpreet Algebra 4 April 1st, 2008 09:42 AM roadnottaken Algebra 7 August 11th, 2007 03:31 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top