Sign in to follow this  
petya-kurochkin

Why does selection sort have n**2 complexity?

Recommended Posts

I'm wondered why does Selection Sort algorithm have n**2 complexity?

More generally:

Why

for (int i = 0; i < length; i++){

  for(int j = i + 1; j < length; j++) /* */;
}

and 

for (int i = 0; i < length; i++){

  for(int j = 0; j < length; j++) /* */;
}

have the same complexity?

 

As far as I can understand, the first code has N(N+1)/2 = N**2 + N/2 complexity and only the second one has N**2. Isn't it?

Share this post


Link to post
Share on other sites

For talking about complexity, we ignore constant factors. Its all about how the function scales - N^2 means, if you double the elements, the running time quadrupples. It doesn't matter if its 1/2*N^2, N^2, or 100*N^2, scaling always works the same. (For those three: N=2 => 2, 4, 400. N=4 => 8, 16, 1600).

In the same way, only the highest exponent counts. If you've got quadratic scaling, adding (+) a linear scaling (N) still results in a quadratic scaling in the end.

So yeah, a function might have a complexity different than exactly N, N^2... but generall you'll just see O(N^2) since thats just how the notation works. You can easily have a O(N^2) function that runs faster than a O(N) function for small Ns with certain constant factors. But eventually the O(N) will always be faster than the O(N^2) function => if you have (n^2)/2 and 10000000n for example, you can calculate the point at which the quadratic scaling will start to be slower (and it will NEVER return to being the other way around at that exact points, thats important) :)

Edited by Juliean

Share this post


Link to post
Share on other sites

Yeah, big-O notation is all about describing what happens when your data set approaches infinity.  N^2 will become so huge that nobody cares about N/2.

 

In that same token, big-O can be very deceiving on what it actually means about performance. See the whole linked-list vs. array debate, where in many cases constant-time linked-list removals are way slower than linear-time array removals.

Edited by SeraphLance

Share this post


Link to post
Share on other sites

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