C
C
CS61B Textbook
Search
⌃K
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
    Θ(log⁡2n)=Θ(log⁡3n)\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⁡2n=log⁡nlog⁡2=Θ(log⁡n)\log_2 n = \frac{\log n}{\log 2} = \Theta(\log n)
. Similarly,
log⁡3n=log⁡nlog⁡3=Θ(log⁡n)\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
Θ(3n)\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
2i2^i
 time. If we run fib for each i from 1 to n, we get a total work of
20+21+...2n2^0 + 2^1 + ... 2^n
. Note that this is a geometric sum with last term
2n2^n
, so the overall runtime is actually still
Θ(2n)\Theta(2^n)
.
Problem 2
Again, we know that fib(i) takes about
2i2^i
 time. However, this time we call fib(n) each time in the loop n total times. This gives a runtime of
Θ(n2n)\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
nn
 total work, and since we halve the input each time, there are
log⁡n\log n
 total levels, for a runtime of
Θ(nlog⁡n)\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:
Θ(n)\Theta(n)
.
Previous
15.5 Summary
Next
16. ADTs and BSTs
Last modified 9mo ago