ComplexityAnalysisLabQuiz.docx

Exercise Suppose we are given three algorithms that solve the same problem, with complexities O(n), O(n2), and O(2n), respectively. Measurement shows that their actual running times on a particular processor are 0.1n seconds, 0.01n2 seconds, and 0.0001* 2n seconds, where n is the number of data item...

Exercise Suppose we are given three algorithms that solve the same problem, with complexities O(n), O(n2), and O(2n), respectively. Measurement shows that their actual running times on a particular processor are 0.1n seconds, 0.01n2 seconds, and 0.0001* 2n seconds, where n is the number of data items to be processed. Complete the table with the largest values of n for which the problem can be solved in a second, a minute, and an hour: Algorithm Running time (seconds) Maximum n in 1 sec Maximum n in 1 min Maximum n in 1 hour A 0.1n B 0.01n2 C 0.0001*2n How much difference does it make if we use a processor that is ten times faster? This reduces each algorithm’s running time by a factor of ten. Calculate the new productivity ratios: Algorithm Running time (seconds) Maximum n in 1 sec Maximum n in 1 min Maximum n in 1 hour A 0.01n B 0.001n2 C 0.00001*2n Which algorithm is the fastest? Which algorithm benefits most from the faster processor? Exercise Suppose that by careful measurement, we have discovered a function T(n) that describes the precise running time of an algorithm. For each of the following such functions, specify their growth rates. T(n) O(g(n)) 10 2 000 000 000 0.3 n , where a,b,c are constants Exercise Arrange the following expressions by growth rate from slowest to fastest: , , , , , , , 3n, 1000 Exercise For each of the following program skeletons, describe the algorithmic growth rate as a function of n. Assume that the remaining portions of the loops require only constant execution time. for (int i=0; i<n; i++) { //... } for (int j=n; j>=0; j--) { //... } for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { //... } } for (int i=0; i<n; i++) { for (int j=0; j<i; j++) { //... } } for (int i=n; i>0; i=i/2) { //... } for (int i=0; i<n; i++) { for (int j=0; j*j<n; j++) { //... } } for (int i=n; i>0; i=i >> 1) { //... } for (long l=n; l>0; l=l >> 2) { for (int j=0; j<n; j++) { //... } }

Show More Show Less