6
$\begingroup$

I'm trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$.

Looking at the math, the runtime is

$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$.

And this is stated to be equal to

$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$.

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

$\endgroup$
  • $\begingroup$ 99% unrelated, 100% out of interest: why'd you use the word "pedagogical"? $\endgroup$ – enche Dec 3 '14 at 19:42
  • $\begingroup$ I just wanted it explained it laymans terms that is understandable :) $\endgroup$ – Pætur Magnussen Dec 4 '14 at 23:32
5
$\begingroup$

Remember what $O(n^2)$ means: it means that there is a constant $c$ such that, for large enough $n$, the number of steps is at most $cn^2$. The constant doesn't have to be $1$; in this case, it looks like the constant is about $\tfrac12$.

Why is $(n-1) + (n-2) + \dots + 2+1$ equal to $O(n^2)$? Because you're adding up $n-1$ numbers and the average of those numbers is half-way between the first one and the last one, i.e., $\tfrac12(1 + (n-1))$. So the total is $$(n-1)\times \tfrac12(1 + (n-1)) = \tfrac12(n^2-n).$$Plug in $n=5000$ and you get... *drumroll*... $12497500$.

$\endgroup$
  • $\begingroup$ Thank you for the answer, but won't the constant then always be 1/2 even as n approaches infinity? $\endgroup$ – Pætur Magnussen Dec 18 '13 at 17:08
  • $\begingroup$ @PæturMagnussen In this case, yes. But that's fine by the definition of $O(-)$. $\endgroup$ – David Richerby Dec 18 '13 at 18:44
  • $\begingroup$ O notation always confuses me. You lost me at "and the average of those numbers is half-way ..." sorry. $\endgroup$ – Ben Dec 3 '14 at 0:13
  • 1
    $\begingroup$ @Ben So substitute your favourite proof that $1 + \dots + k = \tfrac12k(k+1)$ and then substitute $k=n-1$. $\endgroup$ – David Richerby Dec 3 '14 at 0:17
  • 1
    $\begingroup$ @DavidRicherby thanks, and so then from the 0.5(n^2 - n) the big O notation only takes the most significant term which is n^2 (because we treat n as it approaches infinity)? I think I got it now, thanks! $\endgroup$ – Ben Dec 3 '14 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.