My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
will_hunting_math is offline  
 
April 3rd, 2013, 07:16 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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?
CRGreathouse is offline  
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.
will_hunting_math is offline  
April 4th, 2013, 08:10 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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?
CRGreathouse is offline  
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.
will_hunting_math is offline  
April 4th, 2013, 01:57 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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!
CRGreathouse is offline  
April 4th, 2013, 02:10 PM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
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.
will_hunting_math is offline  
April 5th, 2013, 06:35 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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?
CRGreathouse is offline  
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.
will_hunting_math is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2017 My Math Forum. All rights reserved.