Comment on page
15.6 Exercises
Doing more practices is the best way to gain intuition when it comes to asymptotics!
- 1.Prove that.
- 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);
}
- 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);
}
}
- 2.Do the above problem again, but change the body of the for loop in
print_fib
to be:
System.out.println(fib(n));
- 3.Find the runtime of the function
f
on an input of sizen
, given thecreateArray
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.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;
}
}
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: .
Last modified 9mo ago