Complexity Worksheet

1. Express the following running times in big O:
   1. 10n
   2. 10n + 2n²
   3. logn + 5n
   4. n + 2nlogn


2. Consider the following pseudocode:

      tot = 0
      for (i = 0 ; i < n ; i++) {
         C[i] = A[i] + B[i]
         if (A[i] > B[i])
            tot = tot + A[i]
      }
   

   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 accesses, what is the big O complexity of this algorithm?

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

© Copyright Emmi Schatz 2016