go to previous page   go to home page   go to next page

Answer:

(1/2)(N*(N-1))/2  

Average Running Time

So the average running time is proportional to (1/4)( N2 - N)

The N2 term will dominate the equation. So a ball park estimate of running time is:

Average Time ≅ K*N2 for some K

The value of K depends on implementation details and the speed of the computer.

This is the same formula as with selection sort. Running time grows proportionally to the square of the number of items to be sorted. Both selection sort and insertion sort are simple sorts and should not be used for massive data. Other sorting algorithms are much faster (and more complicated). In practice, if you need to sort something, use one of the static methods from the Arrays class from java.util.


QUESTION 10:

The formula above is for the average running time. What is the best running time for insertion sort? Here is the abbreviated algorithm again:

for (int j = 1; j < N; j++)
{
  loop: insert list[j] into its proper place in sub-list of size j
}

The best time would be for an array that was already sorted.


go to previous page   go to home page   go to next page