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

Input:  A length-n array P containing two-dimensional points.
        For example P = [(2.0, 2.3), (1.1, 3.7), (-2.3, 11.0), (4.3, 1.0)]
        
Output: The area of the smallest triangle that can be created by
        selecting three points from P.
        
Algorithm:

* Create an n x n x n three-dimensional array A.

* Populate each entry A[i][j][k] in A with the area of the triangle 
  formed from the i'th, j'th and k'th points from P. 

* Return the smallest non-zero value from A. 

• Worst case or every case?
• Time Complexity class:
• Space usage expressed in asymptotic notation:
• Can you think of any easy ways to improve the efficiency this algorithm?

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;
  }

• Write an English language description of the value returned by this method:  

   

• Worst case or every case?

• Exact growth function:

• 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:
• 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: