# CS 61B

Time: Tue 10/17/17 10 am

## Asymptotic Analysis

### Code Analysis (sp15-mt2-5)

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

### Asymptotics (sp15-mt2-2)

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 ~aNb , and found a and b.Do not leave your answer in terms of logarithms. Your a and b must be within 25% of our answers. Use only the data points that you expect to give the best approximation of the asymptotic behavior of the algorithm.

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 Θ(N2) time. For each of the following, circle the collection type if it is possible for that collection to take Θ(N2) time to insert N items on a worst-case input, and cross out the collection type if it is impossible. Assume that each is correctly implemented.

• 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 Θ(N2), is it always better to use the algorithm that is Θ(N)? If so, why? If not, why not?

### Asymptotics (sp17-mt2-4)

1. 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"); }
}``````
2. 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);
}
}``````