> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/15.-asymptotics-ii/15.6-exercises.md).

# 15.6 Exercises

## Factual

1. Prove that $$\Theta(\log \_{2} n) = \Theta(\log \_{3} n)$$.
2. What is the runtime of the following function?

```java
public static int f(int n) {
    if (n <= 1) {
        return 0;
    }
    return f(n - 1) + f(n - 1) + f(n - 1);
}
```

<details>

<summary>Problem 1</summary>

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

</details>

<details>

<summary>Problem 2</summary>

This is essentially `fib` with 3 recursive calls instead of 2. The runtime is $$\Theta(3^n)$$.

</details>

## Procedural

1. Find the runtime of running `print_fib` with for arbitrarily large n.

```java
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:

```java
 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:

```java
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;
}
```

4. [Problem 8](https://drive.google.com/file/d/1Vo8p4vbOGt7eY5TtalvAEnk4ignpTVvm/view?usp=sharing) from the Spring 2018 Midterm 2
5. [Problem 4](https://drive.google.com/file/d/1yWyRp7QTizspTp9dsKz5yxE6bSf9YUIi/view?usp=sharing) from the Spring 2017 Midterm 2

<details>

<summary>Problem 1</summary>

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)$$.

</details>

<details>

<summary>Problem 2</summary>

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)$$.

</details>

<details>

<summary>Problem 3</summary>

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)$$.

</details>

<details>

<summary>Problem 4</summary>

[Solutions](https://drive.google.com/file/d/1LIyFXwHYCWXNqIgKTsTyKiOYnB79_ykk/view?usp=sharing) and [walkthrough](https://www.youtube.com/watch?v=nMZn4EV0gGw) are linked here and on the course website.

</details>

<details>

<summary>Problem 5</summary>

[Solutions](https://drive.google.com/file/d/1b99XARlZxg3NMfeSAVt2yzDzwSEcASq3/view?usp=sharing) are linked here and on the course website.

</details>

## 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.

```java
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;
   }
}  
```

<details>

<summary>Problem 1</summary>

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)$$.

</details>