182 Chapter 4. Algorithm Analysis

4.5 Exercises Reinforcement

R-4.1 Graph the functions 8n, 4nlogn, 2n2, n3, and 2n using a logarithmic scale for the x- and y-axes; that is, if the function value f(n) is y, plot this as a point with x-coordinate at logn and y-coordinate at logy.

R-4.2 The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n ? n0.

R-4.3 The number of operations executed by algorithms A and B is 40n2 and 2n3, respectively. Determine n0 such that A is better than B for n ? n0.

R-4.4 Give an example of a function that is plotted the same on a log-log scale as it is on a standard scale.

R-4.5 Explain why the plot of the function nc is a straight line with slope c on a log-log scale.

R-4.6 What is the sum of all the even numbers from 0 to 2n, for any integer n ? 1?

R-4.7 Show that the following two statements are equivalent: (a) The running time of algorithm A is always O(f(n)). (b) In the worst case, the running time of algorithm A is O(f(n)).

R-4.8 Order the following functions by asymptotic growth rate. 4nlogn+2n 210 2logn 3n+100logn 4n 2n n2 +10n n3 nlogn

R-4.9 Give a big-Oh characterization, in terms of n, of the running time of the example1 method shown in Code Fragment 4.12.

R-4.10 Give a big-Oh characterization, in terms of n, of the running time of the example2 method shown in Code Fragment 4.12.

R-4.11 Give a big-Oh characterization, in terms of n, of the running time of the example3 method shown in Code Fragment 4.12.

R-4.12 Give a big-Oh characterization, in terms of n, of the running time of the example4 method shown in Code Fragment 4.12.

R-4.13 Give a big-Oh characterization, in terms of n, of the running time of the example5 method shown in Code Fragment 4.12.

R-4.14 Show that if d(n) is O(f(n)), then ad(n) is O(f(n)), for any constant a > 0.

R-4.15 Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then the product d(n)e(n) is O(f(n)g(n)).

R-4.16 Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n) + e(n) is O(f(n) + g(n)).

4.5. Exercises 183 1 /?? Returns the sum of the integers in given array. ?/ 2 public static int example1(int[ ] arr) { 3 int n = arr.length, total = 0; 4 for (int j=0; j < n; j++) // loop from 0 to n-1 5 total += arr[j]; 6 return total; 7 } 8 9 /?? Returns the sum of the integers with even index in given array. ?/ 10 public static int example2(int[ ] arr) { 11 int n = arr.length, total = 0; 12 for (int j=0; j < n; j += 2) // note the increment of 2 13 total += arr[j]; 14 return total; 15 } 16 17 /?? Returns the sum of the prefix sums of given array. ?/ 18 public static int example3(int[ ] arr) { 19 int n = arr.length, total = 0; 20 for (int j=0; j < n; j++) // loop from 0 to n-1 21 for (int k=0; k <= j; k++) // loop from 0 to j 22 total += arr[j]; 23 return total; 24 } 25 26 /?? Returns the sum of the prefix sums of given array. ?/ 27 public static int example4(int[ ] arr) { 28 int n = arr.length, prefix = 0, total = 0; 29 for (int j=0; j < n; j++) { // loop from 0 to n-1 30 prefix += arr[j]; 31 total += prefix; 32 } 33 return total; 34 } 35 36 /?? Returns the number of times second array stores sum of prefix sums from first. ?/ 37 public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays 38 int n = first.length, count = 0; 39 for (int i=0; i < n; i++) { // loop from 0 to n-1 40 int total = 0; 41 for (int j=0; j < n; j++) // loop from 0 to n-1 42 for (int k=0; k <= j; k++) // loop from 0 to j 43 total += first[k]; 44 if (second[i] == total) count++; 45 } 46 return count; 47 } Code Fragment 4.12: Some sample algorithms for analysis