Analysis Exercises

For each of the algorithm listings below:

• Determine if a worst-case or every case analysis is appropriate. You can express worst case as \(W(n)\) and every case as \(T(n)\).
• Determine a basic operation to count (if one is not provided).
• Provide a growth function describing the exact operation count as a function of the input size.
• Describe the running time in terms of big-\(\Theta\) (or big-O if only an upper bound can be provided).

Listing 1

Count all assignments to sum.

  public static int someFunc1(int[] numbers) {
    int sum = 0;

    for (int num : numbers) {
      sum += num;
      for (int i = 0; i < 20; i++) {
        sum += i;
      }
    }
    return sum;
  }

• Worst case or every case?
• Exact growth function:
• Complexity class:

Listing 2

Count all assignments to sum.

  public static int fun(int[] numbers) {
    int sum = 0;

    for (int i = 0; i < numbers.length; i++) {
      sum += numbers[i];
      for (int j = i; j < numbers.length; j++) {
        sum += numbers[i] * numbers[j];
      }
    }
    return sum;

  }

• Worst case or every case?
• Exact growth function:
• Complexity class:

Listing 3

Count assignments to s.

  PROCEDURE DoStuff(numbers1, numbers2)
    s <- 0
    
    FOR x IN numbers1 DO
      FOR y IN numbers2 DO
         IF x < y DO
           RETURN 0
         ELSE
           s <- s + x
         ENDIF
       ENDFOR
    ENDFOR
    
    FOR x IN numbers2 DO
      s <- s + x
    ENDFOR
    
    RETURN s
  

• Worst case or every case?
• How should we represent the input size? (Notice that the procedure has two parameters.)
• Exact growth function:
• Complexity class:

Listing 4

Select an appropriate basic operation.

  public static int fun3(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {

    int overlap = 0;
    for (int num : nums1) {
      if (nums2.contains(num)) {
        overlap++;
      }
    }
    return overlap;
  }

• Worst case or every case?
• Exact growth function:
• Complexity class:

Listing 5

Use incrementing sum as the basic operation. For the sake of simplicity, you may assume that the length of numbers is a power of 2.

   public static int fun4(int[] numbers) {
    int sum = 0;
    for (int i = numbers.length - 1; i >= 1; i /= 2) {
      for (int j = 0; j < numbers.length / 2; j++) {
        sum++;
      }
    }
    return sum;
  }

• Worst case or every case?
• Exact growth function:
• Complexity class:

Listing 6

   public static int fun5(int[] numbers) {
    int sum = 0;
    for (int i = 0; i < numbers.length; i++) {
        flibbert(numbers); // We know that flibbert requires fewer than
                           // n^2 operations in the worst case. 
    }
    return sum;
  }

• Worst case or every case?
• Exact growth function:
• Complexity class: