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: 933 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: 933 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Lower and upper bounds Quote:
 
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: 933 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: 933 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 comparisonbased 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 comparisonbased 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 comparisonbased 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: 933 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Lower and upper bounds Quote:
 
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 comparisonbased 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 comparisonbased 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 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Upper and lower bounds theorems  p99410  Algebra  2  December 17th, 2013 03:08 PM 
Help with upper/lower bounds in GCSE stats  adamj6100  Algebra  1  October 23rd, 2010 11:15 AM 
Asymptotic lower/upper bounds for unconventional T(n)?  Shaitan00  Applied Math  10  September 21st, 2008 09:09 AM 
Upper lower bounds  Kiranpreet  Algebra  4  April 1st, 2008 09:42 AM 
Upper and Lower Bounds of roots  roadnottaken  Algebra  7  August 11th, 2007 03:31 AM 