Comment on page

# 15.6 Exercises

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

- 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);

}

- 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 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.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: $\Theta(n)$

.Last modified 9mo ago