Complexity Worksheet Answers

1. Express the following running times in big O:
   1. O(n)
   2. O(n²)
   3. O(n)
   4. O(n log n)


2. Consider the following pseudocode:

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

   Statement	Count	Array Refs
   (1)	1	0
   (2)	n+1	0
   (3)	n	3n
   (4)	n	2n
   (5)	n	n

   The total number of array accesses is 6n. The algorithm is O(n).




---

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

© Copyright Emmi Schatz 2016