Complexity Worksheet Two Answers

1. In the worst case, each statement is executed as follows:

   (1)     numfive = 0;
   (n+1)   for (i = 0 ; i < n ; i++) {
   (n)      if (arr[i] == 5) {
   (n)         numfive++;
           }
   

   Since there is one array reference in the if statement, there are n array references in the worst case. Therefore, counting array references, the big O complexity of this algorithm is O(n).


2. 1. In the worst case, each statement is executed as follows:

      (1)       tot = 0;
      (N+1)     for (i = 0 ; i < N ; i++) {
      N(M+1)       for (j = 0 ; j < M ; j++) {
      MN              if (arr[i][j] > 0) {
      MN                 tot = tot + arr[i][j];
      MN                 arr[i][j] = 0;
                      }
                   }
                }
      

      The total number of statements executed in the worst case is 4MN + 2N + 2
   2. The complexity in the worst case is O(MN).
   3. In the best case, each statement is executed as follows:

      (1)       tot = 0;
      (N+1)     for (i = 0 ; i < N ; i++) {
      N(M+1)       for (j = 0 ; j < M ; j++) {
      MN              if (arr[i][j] > 0) {
      0                  tot = tot + arr[i][j];
      0                  arr[i][j] = 0;
                      }
                   }
                }
      

      The total number of statements executed in the best case is 2MN + 2N + 2
   4. The complexity in the best case is O(MN).

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2016