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 what n represents for this analysis. In other words, how are we measuring the size of the input?
• Determine a basic operation to count (if one is not provided).
• Provide a function describing the operation count as a function of the input size.
• Determine the big-\(\Theta\) complexity class.

Listing 1

Count all arithmetic operations.

  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?
• What does \(n\) represent in this analysis?
• Exact growth function:
• Big-\(\Theta\) complexity class:

Listing 2

Count all arithmetic operations.

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

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

  }

• Worst case or every case?
• What does \(n\) represent in this analysis?
• Exact growth function:
• Big-\(\Theta\) 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:
• Big-\(\Theta\) complexity class:

Listing 4

Count all arithmetic operations.

  public static int fun2(String sentence) {

    int[] counts = new int[sentence.length()];

    for (int i = 0; i < sentence.length(); i++) {
      for (int j = i; j < sentence.length(); j++) {
        if (sentence.charAt(i) == sentence.charAt(j)) {
          counts[i] += 1;
        }
      }
    }

    int howMany = 0;
    for (int count : counts) {
      if (count > 1) {
        howMany++;
      }
    }
    return howMany;
  }

• Worst case or every case?
• What does \(n\) represent in this analysis?
• Exact growth function:
• Big-\(\Theta\) complexity class:
• Question: Have we chosen the best basic operation here? Can you think of a different choice that would simplify the analysis, but lead to the same big-\(\Theta\) complexity class?

Listing 5

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:
• Big-\(\Theta\) complexity class:

Listing 6

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:
• Big-\(\Theta\) complexity class:

Listing 7

   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?