15.6 Exercises

Doing more practices is the best way to gain intuition when it comes to asymptotics!

Factual

1. Prove that $\Theta(\log _{2} n) = \Theta(\log _{3} n)$.

2. What is the runtime of the following function?

public static int f(int n) {
    if (n <= 1) {
        return 0;
    }
    return f(n - 1) + f(n - 1) + f(n - 1);
}

Problem 1

Using the properties of logs, we see that $\log_2 n = \frac{\log n}{\log 2} = \Theta(\log n)$. Similarly, $\log_3 n = \frac{\log n}{\log 3} = \Theta(\log n)$. So when consiering asymptotics relating to logarithms, the base does not matter (as long as it is some constant).

Problem 2

This is essentially fib with 3 recursive calls instead of 2. The runtime is $\Theta(3^n)$.

Procedural

1. Find the runtime of running print_fib with for arbitrarily large n.

public void print_fib(int n) {
   for (int i = 0; i < n; i++) {
       System.out.println(fib(i));
   }
}

public int fib(int n){
   if (n <= 0) {
     return 0;
   } else if (n == 1) {
     return 1;
   } else {
     return fib(n-1) + fib(n-2);
   }
}

1. Do the above problem again, but change the body of the for loop in print_fib to be:

 System.out.println(fib(n));

1. Find the runtime of the function f on an input of size n, given the createArray function as described below:

public static void f(int n) {
    if (n == 1) {
        return;
    }
    f(n / 2);
    f(n / 2);
    createArray(n);
}

public int[] createArray(int Q) {
    int[] x = new int[Q];
    for (int i = 0; i < x.length; i++) {
        x[i] = i;
    }
    return x;
}

1. Problem 8 from the Spring 2018 Midterm 2
2. Problem 4 from the Spring 2017 Midterm 2

Problem 1

From lecture, we know that fib(i) runs in roughly $2^i$ time. If we run fib for each i from 1 to n, we get a total work of $2^0 + 2^1 + ... 2^n$. Note that this is a geometric sum with last term $2^n$, so the overall runtime is actually still $\Theta(2^n)$.

Problem 2

Again, we know that fib(i) takes about $2^i$ time. However, this time we call fib(n) each time in the loop n total times. This gives a runtime of $\Theta(n2^n)$.

Problem 3

This function creates two recursive branches of half the size per call, with each node taking linear work. As such, each level has $n$ total work, and since we halve the input each time, there are $\log n$ total levels, for a runtime of $\Theta(n \log n)$.

Problem 4

Solutions and walkthrough are linked here and on the course website.

Problem 5

Solutions are linked here and on the course website.

Metacognitive

1. What would the runtime of modified_fib be? Assume that values is an array of size n. If a value in an int array is not initialized to a number, it is automatically set to 0.

public void modified_fib(int n, int[] values) {
   if (n <= 1) {
     values[n] = n;
     return n;
   } else {
     int val = values[n];
     if (val == 0) {
       val = modified_fib(n-1, values) + modified_fib(n-2, values);
       values[n] = val;
     }
     return val;
   }
}  

Problem 1

This is an example of dynamic programming, a topic covered in more depth in CS170. Note that since values is saved across calls, we only recompute each value of n once. Computing a single value of n only takes constant time, since we just add two already-computed values or do an array access. As such, the overall runtime is linear: $\Theta(n)$.