petya-kurochkin 141 Report post Posted April 23 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? 0 Share this post Link to post Share on other sites
Juliean 7079 Report post Posted April 23 (edited) 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 April 23 by Juliean 3 Share this post Link to post Share on other sites
petya-kurochkin 141 Report post Posted April 23 only the highest exponent counts Wow, I didn't know about that! Thank you very much! :) 0 Share this post Link to post Share on other sites
SeraphLance 2607 Report post Posted April 23 (edited) 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 April 23 by SeraphLance 1 Share this post Link to post Share on other sites