# Why does selection sort have n**2 complexity?

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

## 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 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 on other sites

only the highest exponent counts

Wow, I didn't know about that! Thank you very much! :)

##### 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

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633696
• Total Posts
3013394
×