Complexity Worksheet Two

1. Consider the following pseudocode:

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

   In the worst case, how many times is each statement executed? Count the total number of references to array elements in the worst case. If the operation we are counting is array references, what is the big O complexity of this algorithm?


2. Consider the following pseudocode:

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

   1. In the worst case, how many times is each statement executed?
   2. What is the big O complexity of this algorithm in the worst case?
   3. In the best case, how many times is each statement executed?
   4. What is the big O complexity of this algorithm in the best case?

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

© Copyright Emmi Schatz 2016