Assume you have to sort an array with n = 1,000,000 elements. How long would insert sort and heapsort roughly need assuming each basic step takes one milli-second?
I know that insert sort takes n^2 steps in the worst case, and heapsort takes n log n steps in the worst case.
So 1,000,000 ^ 2 for insertion sort = 1*10^12 milli-seconds
and 1,000,000 * log(1,000,000) for heap-sort? 6,000,000 milli-seconds
is that correct?
Well...
The problem is that "order" notation is only talking about limits and comparisons, not absolute times. It also leaves off constants and lower order terms.
For example (this is totally fictitious), the actual running time for the specific insertion sort implementation you might be looking at could be:
num steps = 45,334 * n^2 + 6,500,000 * n + 2,000,000
That is an O(n^2) algorithm, but it'll take a lot more time than what you've computed.