What is the worst case scenario for insertion sort O(n^2)?

Question

What is the worst case scenario for insertion sort O(n^2)?

it strikes me that if the array to be sorted is already sorted in reverse order then the first element is compared 0 times the second 1 time, the third 2 times and so on and so the total time should equal the SUM {i=1->i=(n-1)} [n] but that doesn't equal n^2 (for example if n=4 then that sum is 1+2+3=6.

this website says its because each insertion takes O(n) and theres n of those so thats O(n^2). but why does each insertion take O(n), the first one doesn't so onlyl n-1 insertions could take O(n) but neither does the second one and so on. only the insertions towards infinity take O(n) to insert. (is it becuase theres an infinite number of elements with insirtion=O(n) and so the oens where insertion takes

Answer 1

O(n^2) does not mean the operation will take n^2 steps... Only that the number of steps involved is (approximately) n^2 times some constant value.

In this case, your number of steps should remind you of Gauss triangle numbers. Thus, that value for n-1 is n*(n-1)/2, and as for large numbers n-1 is very close to n, you can approximate this value by (n^2)/2 (and thus, the multiplication constant is 1/2).

Answer 2

Your example is correct.

O(n²) means proportional to n² as n approaches infinity, not necessarily equal n² for all n.

More precisely, to show that f(n) and g(n) are proportional as n grows to infinity, you need to show

\lim_{n\to \infty}\frac{f(n)}{g(n)} = c http://www.texify.com/img/%5CLarge%5C%21%5Clim_%7Bn%5Cto%20%5Cinfty%7D%5Cfrac%7Bf%28n%29%7D%7Bg%28n%29%7D%20%3D%20c.gif

for some finite nonzero constant c. In this case, you get something like

\lim_{n\to \infty}\frac{n^2}{\left(\frac{n^2+n}{2}\right)} = 2 http://www.texify.com/img/%5CLarge%5C%21%5Clim_%7Bn%5Cto%20%5Cinfty%7D%5Cfrac%7Bn%5E2%7D%7B%5Cleft%28%5Cfrac%7Bn%5E2%2Bn%7D%7B2%7D%5Cright%29%7D%20%3D%202.gif