CP164 Study Guide - Final Guide: Selection Sort, If And Only If
Algorithm Analysis
Can we be more precise? What do we mean by proportional to? Twice a long? Ten times as
long?
The following table and graph show running times for the Selection Sort on different
platforms:
Selection Sort Times (ms)
Array Size (n)
Platform 1
Platform 2
125
12.5
2.8
250
49.3
11.0
500
195.8
43.4
1000
780.3
172.9
2000
3164.9
690.5
And a graph of this data:
Two Curves Fitting the Table Data
Both curves are quadratic and generated by these equations:
• f1(n) = 0.0007772n2 + 0.00305n + 0.001
• f2(n) = 0.0001724n2 + 0.00040n + 0.100
What if we use a very large data set? (e.g. n = 100,000):
• f1(100,000) = 7,772,000 + 305 + 0.001
• f2(100,000) = 1,724,000 + 40 + 0.100
Note that the n2 terms are by far the dominant terms as n grows in size. Thus the execution
time of Selection Sort is dominated by the n2 terms when n is large. The n and constant
terms are significant only when n is small.
The coefficients of n2 are also less important because they depend on the environment the
algorithm is running on.
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
The following table and graph show running times for the selection sort on different platforms: Both curves are quadratic and generated by these equations: f1(n) = 0. 0007772n2 + 0. 00305n + 0. 001 f2(n) = 0. 0001724n2 + 0. 00040n + 0. 100. What if we use a very large data set? (e. g. n = 100,000): f1(100,000) = 7,772,000 + 305 + 0. 001 f2(100,000) = 1,724,000 + 40 + 0. 100. Note that the n2 terms are by far the dominant terms as n grows in size. Thus the execution time of selection sort is dominated by the n2 terms when n is large. The n and constant terms are significant only when n is small. The coefficients of n2 are also less important because they depend on the environment the algorithm is running on. We can classify the performance of an algorithm, specifically their growth rates, with big-o notation.
