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 Θ(N²) 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 ~aN^b , 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.

Suppose we measure the performance of a collection X, and find that inserting N items takes Θ(N²) time. For each of the following, circle the collection type if it is possible for that collection to take Θ(N²) 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.

• 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²), 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);
    }
  }
}