Sign in to follow this  

complexity of bubble sort

This topic is 4842 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, how is the time required to execute bubble sort is proportional to O(n^2). I m asking this question because when i tried to calculate it myself the result was different. It is obvious that i m doing something wrong here. but any way here i go. The algorithm requires (n-1) comparasions in first pass and the subsequent passes requires one comparasion less the previous pass which means total comparasions are: total comparasions = (n-1)+(n-2)+ .....+3+2+1 = (n*(n-1))/2 now if we ignore 1 we get = (n^2)/2 this is the result i calculated which is half of what the actual result is. What am i doing wrong here. please help thanx bye

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
All constants should be removed when calculating complexity...

Share this post


Link to post
Share on other sites
yup, generally constants are omitted. And big-O usually implies (though might be wrong) the worst case scenario. So comparing n^2/2 and n^2... i think n^2 is worse :P Its as bad as it can get.

Share this post


Link to post
Share on other sites
O() assumes you look at massive data sets, so n gets SO big none of the other numbers matter.

What's the difference between 1 bazillion / 2 and 1.3 bazillion / 2?
It's so small, we ignore them.

Share this post


Link to post
Share on other sites
Quote:
O() assumes you look at massive data sets, so n gets SO big none of the other numbers matter.


Erm.. not really..
The reason O encapsulates all the constants in the expression, is the notation is given to measure the performance characteristics of the algorithm relative to the size of its dataset.

Share this post


Link to post
Share on other sites
Big-O notation measures the order of the running time (or memory usage). The only important part is the largest term in the expression; all other terms and coefficients can be ignored.

For example:
If the running time is calculated as 2n2 + 3n, then the order of the expression is O(n2). As n goes to infinity, n2 becomes much larger than n, so the n term is irrelevent.

Selection sort, insertion sort, and bubble sort are all O(n2) in their average-case; in reality, their running times differ because of the dropped constants. Big-O is only a hint to the potential running time, not a definitive statement.

Share this post


Link to post
Share on other sites
This is essentially a restatement of the previous poster...

Big-O measures what function order you're looking at. Roughly speaking, this means that you consider the function in lim n->infinity. All constants drop out, and all except the highest order n term drop. So if a algorithm is n^2 + 2n + 5, for example, that is O(n^2).

Share this post


Link to post
Share on other sites
Hi,

if big Oh does not give the actual execution time and is just an approximation like u said Selection sort, insertion sort, and bubble sort give the same O(n^2) although they have actually different execution time, What is the practical use of big oh then. Isn't bench marking a better way?Why is this algorithm complexity analysis so important in computer science?

thanx

Share this post


Link to post
Share on other sites
- It is a precisely-defined mathematical concept. Deal with it.
- You are evaluating algorithms asymptotic behavior, not implementation details or hardware performance.
- Algorithm complexity has scalability implications.
- Even with O() notation, you can still discuss Best/Average/Worst case performance.

O(n^2) is as bad as it can get for comparison-based sorting algoriths. Good algorithms run in O(n*log n). Of course, the constants do matter in practice, which is why good sort() routines will first check the value of n and pick an algorithm or another (insertion heap sort for small data sets, quicksort for larger data sets) so that you get the best performance.

edit - Little Washuuuuuuuuu corrected me.

[Edited by - Fruny on September 12, 2004 9:33:01 PM]

Share this post


Link to post
Share on other sites
Think of Big-O notation not as an assessment of an algorithm's performance but rather as an assessment of how much slower an algorithm gets as n increases without bound.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
- It is a precisely-defined mathematical concept. Deal with it.
- You are evaluating algorithms asymptotic behavior, not implementation details or hardware performance.
- Algorithm complexity has scalability implications.
- Even with O() notation, you can still discuss Best/Average/Worst case performance.

O(n^2) is as bad as it can get for comparison-based sorting algoriths. Good algorithms run in O(n*log n). Of course, the constants do matter in practice, which is why good sort() routines will first check the value of n and pick an algorithm or another (insertion sort for small data sets, quicksort for larger data sets) so that you get the best performance.

Hrm, Introspective sort generally has a better worst time bound than quicksort (as it will switch to a heapsort when it encounters to many bad chunks.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Buzz1982
Why is this algorithm complexity analysis so important in computer science?

Algorithms are our swords and shields; whether we live or die depends on how sharp they are.

Share this post


Link to post
Share on other sites
Quote:
Original post by Buzz1982
Why is this algorithm complexity analysis so important in computer science?

Have you ever tried to sort a few billion elements? Well, knowing algorithm complexity of your sorting algorithm can tell you aproximately how long it will take for it to sort, both in the worst case, and in the best case. This can affect your choice of algorithms.
Things like: Choosing a hashtable over a balanced tree. The hashtable has an average complexity of O(1) for a lookup, but a worst case bound of O(n)1. On the other hand, a balanced tree gives O(log n) average and worst case lookup times.

So, if your average case is the primary concern, use a hashtable. However, if your worst case scenerio is the concern, then use a balanced tree (std::set/std::multiset/std::map/std::multimap)

1 This is for a general implementation of a hash table, there are specializations that you can do to reduce this, but in general the worst case time of a hash table is worse than that of a balanced tree.

Share this post


Link to post
Share on other sites
Quote:
Original post by Buzz1982
Hi,

if big Oh does not give the actual execution time and is just an approximation like u said Selection sort, insertion sort, and bubble sort give the same O(n^2) although they have actually different execution time, What is the practical use of big oh then. Isn't bench marking a better way?Why is this algorithm complexity analysis so important in computer science?

thanx

Benchmarking depends on implementation and hardware details. O() is a mathematical, theoretical look at problems. There are more specific complexities that don't drop constants, but big-O is used as a general barometer since it shows how an algorithm will work with increasing load. As the dataset approaches infinity, the algorithm with the better big-O complexity will win.

You are right in that you should look at algorithms more closely than just following big-O complexities. For example, bubble sort is O(n) on a presorted list where as quicksort is O(n^2). There is a modified version of mergesort that works on large databases where most of the data is on disk that works in essentially O(n) time since disk reads take such an enormous amount of time compared to a memory comparison. So big-O is really just a guide, but doesn't tell the whole story. Kind of like a baseball player's batting average. You really need to know HR, RBI, Slugging, and on base to get a good idea of how a player is performing, but the batting average is a good indicator of those other stats.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
- It is a precisely-defined mathematical concept. Deal with it.
- You are evaluating algorithms asymptotic behavior, not implementation details or hardware performance.
- Algorithm complexity has scalability implications.
- Even with O() notation, you can still discuss Best/Average/Worst case performance.

O(n^2) is as bad as it can get for comparison-based sorting algoriths. Good algorithms run in O(n*log n). Of course, the constants do matter in practice, which is why good sort() routines will first check the value of n and pick an algorithm or another (insertion heap sort for small data sets, quicksort for larger data sets) so that you get the best performance.

edit - Little Washuuuuuuuuu corrected me.
Um, can I correct Washu then? Introspective sort only switches to heap sort when the running time is becomming quadratic, NOT because the current recursive call has only a small number of elements to sort.

Using a specially constructed pathological case of 1-million elements you could find that is does a heap sort on 900-thousand elements for example.

Insertion Sort is generally faster than HeapSort for small enough arrays (say < 16). Insertion Sort is also used when the data is possibly large but nearly sorted as in the common final pass to quicksort.

You have heard of things like Permutation Sort too right Fruny? O(n*(n!)). Yes no sensible algorithm is worse than O(n*n).

Buzz1982: Well done. I trust you understand what the others have already told you. Now try and calculate the O notation for ShellSort with Donald Shell's original step-sizes!!! (J/K)

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Um, can I correct Washu then? Introspective sort only switches to heap sort when the running time is becomming quadratic, NOT because the current recursive call has only a small number of elements to sort.

Using a specially constructed pathological case of 1-million elements you could find that is does a heap sort on 900-thousand elements for example.

Then I shall correct you! Muahahaha
I never said for small numbers of elements. I just said that when it encountered a number of bad chunks (for QS). Which is when it goes to the quadratic bound.
Quote:

Insertion Sort is generally faster than HeapSort for small enough arrays (say < 16). Insertion Sort is also used when the data is possibly large but nearly sorted as in the common final pass to quicksort.

Yes, this is true, but for a case of <16, there is no reason to care (if your objects are large, use pointers)
Quote:

You have heard of things like Permutation Sort too right Fruny? O(n*(n!)). Yes no sensible algorithm is worse than O(n*n).

Buzz1982: Well done. I trust you understand what the others have already told you. Now try and calculate the O notation for ShellSort with Donald Shell's original step-sizes!!! (J/K)

Permutation sorts...gods above, Smite this heathen!

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Buzz1982: Well done. I trust you understand what the others have already told you. Now try and calculate the O notation for ShellSort with Donald Shell's original step-sizes!!! (J/K)


O_o

ShellSort is actually named after a d00d? I always assumed the name referred to a metaphorical collecting of the elements into "shells" and playing a "shell game" with them, as it were. :s

Share this post


Link to post
Share on other sites
Quote:
Original post by Washu
Quote:
Original post by iMalc
Um, can I correct Washu then? Introspective sort only switches to heap sort when the running time is becomming quadratic, NOT because the current recursive call has only a small number of elements to sort.

Using a specially constructed pathological case of 1-million elements you could find that is does a heap sort on 900-thousand elements for example.

Then I shall correct you! Muahahaha
I never said for small numbers of elements. I just said that when it encountered a number of bad chunks (for QS). Which is when it goes to the quadratic bound.

Okay maybe I misinterpreted something.
Quote:

Quote:

Insertion Sort is generally faster than HeapSort for small enough arrays (say < 16). Insertion Sort is also used when the data is possibly large but nearly sorted as in the common final pass to quicksort.

Yes, this is true, but for a case of <16, there is no reason to care (if your objects are large, use pointers)

Agreed, assuming it isn't used as part of a better sorting algorithm where it's repeated a lot for small sub-arrays.
Quote:

Permutation sorts...gods above, Smite this heathen!

Oh, and I mustn't forget good old StoogeSort O(n^2.7), StupidSort O(n^3), FibSort, BogoSort...
:P

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by iMalc
Buzz1982: Well done. I trust you understand what the others have already told you. Now try and calculate the O notation for ShellSort with Donald Shell's original step-sizes!!! (J/K)


O_o

ShellSort is actually named after a d00d? I always assumed the name referred to a metaphorical collecting of the elements into "shells" and playing a "shell game" with them, as it were. :s
That's what I once thought once too. It's doubly appropriate I think. It's approximately O(n^1.5) btw, but I'll be damned if I could even prove it.

You live you learn!

Share this post


Link to post
Share on other sites

This topic is 4842 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this