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

Answer:

(N-1) + (N-2) + (N-3) + (N-4) + ... + 3 + 2 + 1 = N*(N-1)/2

Quadratic

This is N2/2 - N/2. The running time of selection sort is proportional to the square of how many integers are sorted. In other words,

Time ≅ K*N2 for some K.

The N/2 term can be ignored since the quadratic term will dominate.

Say it takes 3 seconds to sort 50 thousand integers. How long will it take to sort 100 thousand integers?

3 sec = K*N2, for N = 50 thousand.
K = 3 sec/N2

100 thousand integers = 2*N
time = K*(2*N)2 = 3 sec/N2 * 4 * N2
time = 12 sec

The easy way to do this is to realize that if time is proportional to the square of items to be sorted, then if there are twice as many items it will take four times as long.

Say that the number of integers is increased by a factor of three to 150 thousand integers. Time will increase by a factor of nine. It will take 27 seconds to sort 150 thousand integers.

On a faster computer, K will be different, so perhaps it takes 1 second to sort 50 thousand integers. It will then take 4 seconds to sort 100 thousand integers, and 9 seconds to sort 150 thousand.

This topic, the analysis of algorithms, is an important one in computer science. It is covered at depth in upper level CS courses.


QUESTION 12:

Say that it takes 3 seconds to sort 50 thousand integers on my computer. How long would it take to sort a million integers?

Hint: one million is 20 times 50 thousand.


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