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?

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Dec 18, 2013 at 17:08
  • $\begingroup$ @PæturMagnussen In this case, yes. But that's fine by the definition of $O(-)$. $\endgroup$
    – David Richerby
    Commented Dec 18, 2013 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
    Commented Dec 3, 2014 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
    Commented Dec 3, 2014 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
    Commented Dec 3, 2014 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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