Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: Lower Bound Proofs

btw, do you think this should be moved to Coders Corner?

---

A logarithm is just a misspelled algorithm.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Lower Bound Proofs

I'm going to be attempting to illustrate something that I've waved my hands at, and really should have covered first.  Then hopefully we can move on to some more interesting problems.

Now do the same analysis for bubblesort, but this time by counting a single swap as a cost of 1, everything else counts as 0.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: Lower Bound Proofs

single swap = 1, everything else is zero?
Do you mean the total number of swaps, best and worst case?

---

A logarithm is just a misspelled algorithm.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Lower Bound Proofs

Corret.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: Lower Bound Proofs

Last edited by mikau (2007-08-01 02:27:36)

---

A logarithm is just a misspelled algorithm.

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: Lower Bound Proofs

are those solutions correct, Ricky?

---

A logarithm is just a misspelled algorithm.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Lower Bound Proofs

Sorry, must have overlook this.  Yes, those are correct.  So here is the thing about models.  We have two models:

A. Count the number of list comparisons.
B. Count the number of swaps.

Both can be applied to bubble sort.  And we have the best and worst cases as follows:

          |  A         |     B
-------------------------------
Worst  |  n^2     |     n^2
-------------------------------
Best    |  n         |     0

Now the question becomes which is a better model, A or B?  There is a very specific answer to this question.  But it is a more of a think-about-it-yourself-for-a-bit-then-I'll-tell-you-the-right-answer sort of question.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Lower Bound Proofs

I suppose it depends on how much easier it is to compare the items than to switch them.

For example, say you have a row of books that you want to put in alphabetical order, but some joker has written all the titles in Sanskrit. You need to look up each title in your English-Sanskrit dictionary whenever you want to make a comparison, but once you know the order they should be in, it's a simple matter to put them there.

However, say you have a group of elephants and you want to put them in order of size. It's fairly easy to see which of two elephants is the bigger one, but if they need to be swapped then it'd be fairly tricky to manoeuvre them without getting trunked.

That answer isn't very specific though, so it's probably not what you were thinking of.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Lower Bound Proofs

That is certainly not a wrong answer, but it only skirts the main issue.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."