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.

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:

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:

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:

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?

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:

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:

```
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?