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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/15.-asymptotics-ii/15.6-exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.