Comment on page

# 15.6 Exercises

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

## Factual

1. 1.
Prove that
$\Theta(\log _{2} n) = \Theta(\log _{3} n)$
.
2. 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. 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. 2.
Do the above problem again, but change the body of the for loop in print_fib to be:
System.out.println(fib(n));
1. 3.
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. 4.
Problem 8 from the Spring 2018 Midterm 2
2. 5.
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. 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)$
.