Jump to content
  • Advertisement
Sign in to follow this  
Buzz1982

complexity of bubble sort

This topic is 5147 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
Advertisement
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
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 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!