Time: Tue 10/17/17 10 am

For each of the pieces of code below, give the runtime in *Θ(·)* notation as a function of the given parameters. Your answer should be simple, with no unnecessary leading constants or unnecessary summations.

```
public static void f1(int n) {
for (int i = 0; i < 2 * n; i += 1) {
System.out.println("hello");
}
}
```

```
public static void f2(int n) {
if (n == 0) { return; }
f2(n / 2);
f1(n);
f2(n / 2);
}
```

```
public static void f3(int n) {
if (n == 0) { return; }
f3(n / 3);
f1(n);
f3(n / 3);
f1(n);
f3(n / 3);
}
```

```
public static void f4(int n) {
if (n == 0) { return; }
f4(n - 1);
f1(17);
f4(n - 1);
}
```

```
public static void f5(int n, int m) {
if (m <= 0) {
return;
} else {
for (int i = 0; i < n; i += 1) {
f5(n, m - 1);
}
}
}
```

Suppose we run experiments to understand the runtime performance of the `add`

method of the `PotatoSack`

class. The runtime as a function of N (the number of inserts) is shown below. Using the technique from the asymptotics lab, *approximate* the empirical run time in *tilde notation* as a function of N. As a reminder, in that lab, we assumed that the runtime is *~aN ^{b}* , and found

N | Time (s) |
---|---|

1 | 0.00 |

2 | 0.01 |

3 | 0.01 |

6 | 0.03 |

13 | 0.16 |

25 | 0.63 |

50 | 2.50 |

100 | 9.97 |

Suppose we measure the performance of a collection *X*, and find that inserting *N* items takes *Θ(N ^{2})* time. For each of the following, circle the collection type if it is possible for that collection to take

- LinkedList
- 2-3 Tree Set
- HeapMinPQ
- LLRBST Set
- External Chaining Hash Map
- ArrayList

If we have two correct algorithms for solving the same problem that use the exact same amount of memory, but have worst-case runtimes that are *Θ(N)* and *Θ(N ^{2})*, is it always better to use the algorithm that is

Code:

`public static void f1(int N) { // desired runtime Θ(N) for (int i = 0; i < N; ) { System.output.println("hi"); } }`

`public static void f2(int N) { // desired runtime Θ(logN) for (int i = 0; i < N; ) { System.output.println("hi"); } }`

`public static void f3(int N) { // desired runtime Θ(1) for (int i = 0; i < N; ) { System.output.println("hi"); } }`

Give the runtime of the following function

*Θ(·)*or*O(·)*notations as requested. Your answer should be as simple as possible with no unnecessary leading constants or lower order terms.`public static void f4(int N) { if (N == 0) { return; } f4(N / 2); f4(N / 2); f4(N / 2); f4(N / 2); g(N); // runs in Θ(N^2) time }`

`public static void f5(int N, int M) { if (N < 10) { return; } for (int i = 0; i <= N % 10; i++) { f5(N / 10, M / 10); System.out.println(M); } }`