Problem Set Answers: Complexity

  1. Express the following running times in big O:
    1. O(n)
    2. O(n2)
    3. O(1)
    4. O(n2)
    5. O(n2)
    6. O(n)
    7. O(n log n)
    8. O(n2)
    9. O(n2)

  2. Consider the following pseudocode: 
       count = 0;
   for (i = 1 ; i <= N ; i++)
      count++;
   System.out.println(count);
    1. Statement Worst
      (1) 1
      (2) N+1
      (3) N
      (4) 1
    2. Statement Best
      (1) 1
      (2) N+1
      (3) N
      (4) 1
    3. 1 + N+1 + N + 1 = 2N + 3
    4. 1 + N+1 + N + 1 = 2N + 3
    5. O(N)
    6. O(N)

  3. Consider the following pseudocode: 
       count = 0;
   for (i = 0 ; i < 10 ; i++)
      count++;
   System.out.println(count);
    1. Statement Worst
      (1) 1
      (2) 11
      (3) 10
      (4) 1
    2. Statement Best
      (1) 1
      (2) 11
      (3) 10
      (4) 1
    3. 1 + 11 + 10 + 1 = 23
    4. 1 + 11 + 10 + 1 = 23
    5. O(1)
    6. O(1)

  4. Consider the following pseudocode: 
       count = 0;
   amount = 0;
   for (i = 1 ; i <= N ; i++)
      count++;
   System.out.println(count);
   for (i = 1 ; i < N ; i++)
      arr[i] += count;
    1. Statement Worst
      (1) 1
      (2) 1
      (3) N+1
      (4) N
      (5) 1
      (6) N
      (7) N-1
    2. Statement Worst
      (1) 1
      (2) 1
      (3) N+1
      (4) N
      (5) 1
      (6) N
      (7) N-1
    3. 1 + 1 + N+1 + N + 1 + N + N-1 = 4N + 3
    4. 1 + 1 + N+1 + N + 1 + N + N-1 = 4N + 3
    5. O(N)
    6. O(N)

  5. Consider the following pseudocode: 
       num = 1;
   amount = N;
   amount = amount + N * (N - 1);
   num = num + amount;
    1. Statement Worst
      (1) 1
      (2) 1
      (3) 1
      (4) 1
    2. Statement Worst
      (1) 1
      (2) 1
      (3) 1
      (4) 1
    3. 1 + 1 + 1 + 1 = 4
    4. 1 + 1 + 1 + 1 = 4
    5. O(1)
    6. O(1)

  6. 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]
       }
    1. Statement Worst Case Count Worst Case Array Refs
      (1) 1 0
      (2) n+1 0
      (3) n 3n (3 array references per statement)
      (4) n 2n (2 array references per statement)
      (5) n n (1 array reference per statement)
    2. Statement Best Case Count Best Case Array Refs
      (1) 1 0
      (2) n+1 0
      (3) n 3n (3 array references per statement)
      (4) n 2n (2 array references per statement)
      (5) 0 0
    3. In the worst case the total number of statements executed is 1 + n+1 + n + n + n = 4n + 2 which is O(n).
    4. In the best case the total number of statements executed is 1 + n+1 + n + n = 3n + 2 which is O(n).
    5. The total number of array accesses in the worst case is 6n. The algorithm is O(n).

  7. Consider the following pseudocode: 
       tot = 0
   if ((A[0] == B[0])
      for (i = 1 ; i < n ; i++) {
         C[i] = A[i] + B[i]
         tot = tot + A[i]
   }
    1. Statement Worst Case Count Worst Case Array Refs
      (1) 1 0
      (2) 1 2
      (3) n 0
      (4) n-1 3(n-1) (3 array references per statement)
      (5) n-1 n-1 (1 array reference per statement)
    2. Statement Best Case Count Best Case Array Refs
      (1) 1 0
      (2) 1 2
      (3) 0 0
      (4) 0 0
      (5) 0 0
    3. In the worst case the total number of statements executed is 1 + 1 + n + n-1 + n-1 = 3n which is O(n).
    4. In the best case the total number of statements executed is 1 + 1 + 0 + 0 + 0 = 2 which is O(1).
    5. The total number of array accesses in the worst case is 2 + 3(n-1) + n-1 = 4n-2. The algorithm is O(n).

  8. Consider the following pseudocode: 
       count = 0;
   for (i = 1 ; i <= N ; i++) {
      count++;
      for (k = 1 ; k <= N/4 ; k++)
         arr[k] += count;
   }
   System.out.println(count);
    1. Statement Worst
      (1) 1
      (2) N+1
      (3) N
      (4) N(N/4+1)
      (5) N(N/4)
      (6) 1
      2. Statement Worst
      (1) 1
      (2) N+1
      (3) N
      (4) N(N/4+1)
      (5) N(N/4)
      (6) 1
    2. 1 + N+1 + N + N(N/4+1) + N(N/4) + 1 = 1 + N+1 + N + N2/4+N + N2/4 + 1 = N2/2 + 3N + 3
    3. 1 + N+1 + N + N(N/4+1) + N(N/4) + 1 = 1 + N+1 + N + N2/4+N + N2/4 + 1 = N2/2 + 3N + 3
    4. O(N2)
    5. O(N2)

    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;
                }
             }
          }
    2. There are three array references in the inner loop which each execute mn times in the worst case. Therefore the total number of array references in the worst case is 3mn. If the operation we are counting is array references, the worst case complexity of this algorithm is O(mn).
    3. In the best case, the two array references inside the if never execute, so the total number of array references is mn. If the operation we are counting is array references, the best case complexity of this algorithm is still O(mn).

    1. In the worst case, each statement is executed as follows: 
      (1)        count = 0;
(N+1)      for (int i = 0 ; i < N ; i++)
(N*(N+1))     for (int j = 0 ; j < N ; j++)
(N*N)            if (a[i] + a[j] + a[k] == 0)
(N*N*(N+1)          for (int k = 0 ; k < N ; k++)
(N*N*N)                count++;
      The total of these counts is 2N3 + 3N2 + 2N + 2.
    2. The worst case complexity of this algorithm is O(N3).
    3. In the best case, each statement is executed as follows: 
      (1)        count = 0;
(N+1)      for (int i = 0 ; i < N ; i++)
(N*(N+1))     for (int j = 0 ; j < N ; j++)
(N*N)            if (a[i] + a[j] + a[k] == 0)
(0)                 for (int k = 0 ; k < N ; k++)
(0)                    count++;
      The total of these counts is 2N2 + 2N + 2.
    4. The best case complexity of this algorithm is O(N2).

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

© Copyright Emmi Schatz 2019