complexity of bubble sort

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

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 on other sites
I think you can drop the '/2'.

Share on other sites
All constants should be removed when calculating complexity...

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 on other sites
Hi,

How is n^2 is as bad as it can get, if for the worst situation every subsequent comparasion is one less the previous comparasion. i m confused.

thanx.

Share on other sites
O( Constant * f(n) ) = O( f(n) )
So, in your case: O( (n^2)/2 ) = O( n^2 ).

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 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 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 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).

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 10
• 9
• 15
• 22