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.

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