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