15.6 Exercises

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

Factual

  1. 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
Problem 2

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
Problem 2
Problem 3
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

Last updated