# CS 61B

Time: Tue 10/10/17 5 pm

## Asymptotic Analysis & Amortization

What is asymptotic analysis? We frequently use Θ(·), O(·) and Ω(·), but what are the differences between them? Trivially, the tilde notation strictly defines something similar to the big-theta.

How is amortization related to asymptotic analysis? Think about `ArrayList` as an example with an amortized runtime. Will inserting a single item into an `ArrayList` have a worst runtime of Θ(N2) and a best runtime

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

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