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?