# Asymptotics Practice

{% hint style="warning" %}
Make sure to review [Asymptotic Analysis Basics](https://cs61b.bencuan.me/asymptotics/asymptotics) before proceeding with these problems.
{% endhint %}

## Introduction

Asymptotics is a very intuition-based concept that often doesn't have a set algorithm for computing. The best way to get good at analyzing programs is to practice!

With that said, here are some problems of increasing difficulty for you to enjoy 😊

{% hint style="info" %}
For all of the below problems, assume that all undefined functions have a constant O(1) complexity.
{% endhint %}

## Loops

{% tabs %}
{% tab title="Question 1" %}
What runtime does this function have?

```java
void throwHalfOfMyItems(int n) {
    for (int i = 0; i < n; i += 1) {
        if (i % 2 == 0)
            throwItem(n);
    }
}
```

{% endtab %}

{% tab title="Q1 Answer" %}
$$
\Theta(n)
$$

**Explanation:** The method `throwItem()` runs `n/2` times. Using the simplification rules, we can extract the constant `1/2` to simply get `n`.

![Keep the change, ya filthy animal.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M7-uDnzlxKIWquXKcZe%2Fimage.png?alt=media\&token=062842c1-2687-4888-8101-caba40b25e14)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2a" %}
What runtime does this function have?

```java
void lootShulkerBoxes(int n) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = 0; stack < n; stack += 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}
```

{% endtab %}

{% tab title="Q2a Answer" %}
$$
\Theta(n^2)
$$

**Explanation:** There are **three** nested loops in this problem. Whenever there are nested loops whose runtimes are independent of each other, we need to **multiply** the runtimes in each loop.\
So, we get: $$\Theta(n \* n \* 64)$$ which simplifies into `n^2`

![That's a lot of items to loot...](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M7-vMOc89ynoxqpr6LP%2Fimage.png?alt=media\&token=67d15fa4-83de-43b2-a04b-1a3f7bbdf0b6)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2b" %}
I've tweaked the previous problem a little 😁 Try to spot the difference and see if it changes the runtime at all!

```java
void lootShulkerBoxes(int n, int stacksToLoot) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = stacksToLoot; stack > 0; stack -= 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}
```

{% endtab %}

{% tab title="Q2b Answer" %}
$$
\Theta(n)
$$

**Explanation:** Even though `stacksToLoot` is a user input, we're only concerned about finding the runtime for `n` so `stacksToLoot` can be treated like a constant! Therefore, we now have $$\Theta(n \* s\* 64)$$ where `s = stacksToLoot` which simplifies into `n`.

![ok now this is getting a bit overboard](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M7-xLNR6hR02wyxMPWK%2Fimage.png?alt=media\&token=24da88fa-a0ac-4b4b-9be8-926be9667285)
{% endtab %}
{% endtabs %}

## Recursion

The following two problems are inspired by [this worksheet](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/disc/discussion8.pdf).

{% tabs %}
{% tab title="Question 3" %}
TREEEEEEEEE recursion 🌳🌲🌴

```java
void plantJungleSaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < 4; i += 1) {
            plantJungleSaplings(n - 1);
        }
    }
}
```

{% endtab %}

{% tab title="Q3 Answer" %}
$$
\Theta(4^n)
$$

**Explanation:** This tree recursion creates a tree with `n` layers. Each layer you go down, the number of calls multiplies by 4!

![Tree diagram for method calls.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M70A5zg2LnnV3quKz9F%2Fimage.png?alt=media\&token=ece29415-0a94-4f8e-a8be-a121af1ff8aa)

This means that the number of calls in total will look like this:

$$
\sum\_{i=1}^{n}4^i
$$

And if you remember your power series, you'll know that this sum is equal to $$4^{n+1}-1$$ which simplifies into the final answer.

![an image that makes you long for TreeCapacitator](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M70BCuhYFNRB0PuvoT-%2Fimage.png?alt=media\&token=c2f8864c-3c6c-41de-9970-1e465074cf82)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 4" %}
Let's replace the 4 in the previous problem with **n** and see what insanity ensues.

```java
void plantCrazySaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < n; i += 1) { // This line changed
            plantCrazySaplings(n - 1);
        }
    }
}
```

{% endtab %}

{% tab title="Q4 Answer" %}
$$
\Theta(n!)
$$

**Explanation:** This tree recursion creates a tree with `n` layers. Each layer you go down, the number of calls multiplies by `n-1`...

![What a mess (!)](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M70CYZZvgK996JNQdUd%2Fimage.png?alt=media\&token=b9931af9-b466-44f5-99cf-a033856651e2)

This means that the number of calls in total will look like this:

$$
\sum\_{i=1}^{n} \frac{n!}{i!}
$$

Since `n!` is not dependent on `i` it can be factored out of the sum to produce this:

$$
n!\sum\_{i=1}^{n} \frac{1}{i!}
$$

Hey, that looks a lot like the Taylor series for $$e$$! Since `e` is a constant, it simply reduces to `n!`.
{% endtab %}
{% endtabs %}

## Best and Worst Case Runtimes

{% tabs %}
{% tab title="Question 5" %}
Here's a case where the best case and worst case runtimes are different. Can you figure out what they are? (Let `n = items.length`).

```java
Item[] hopperSort(Item[] items) {
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = items[i]; 
        int j = i - 1; 
        while (j >= 0 && items[j].compareTo(key) > 0) { 
            items[j + 1] = items[j]; 
            j = j - 1; 
        } 
        items[j + 1] = key; 
    } 
}
```

{% endtab %}

{% tab title="Q5 Answer" %}
**Best Case:** $$\Theta(n)$$ if the array is nearly sorted except for a couple values. In this case, the `while` loop will only run a small number of times, so the only loop left is the for loop.

**Worst Case:** $$\Theta(n^2)$$if the array is totally reversed. This will cause the `while` loop to run on the order of `O(n)` times, resulting in a nested loop.

**Note:** HopperSort is literally just Insertion Sort 😎🤣

![hoppers rate 64/64](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M703JY2ft9adFyrCS06%2Fimage.png?alt=media\&token=faf8ad2c-2fbf-4969-bfdb-a3dc18f19480)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 6" %}
Here's a mutual recursion problem! What are the best and worst cases for `explodeTNT(n)`? What are their runtimes?

```java
void explodeTNT(int n) {
    if (n % 2 == 0) {
        digDirts(n - 1, true);
        digDirts(n - 2, false);
    } else {
        digDirts(n / 2, true);
    }
}

void digDirts(int n, boolean isTNT) {
    if (isTNT) {
        explodeTNT(n / 2);
    }
    removeDirt(); // not implemented, assume O(1) runtime
}
```

{% endtab %}

{% tab title="Q6 Answer" %}
**Best Case:** $$\Theta(\log(n))$$ if n is even. This will result in n being halved every function call.

**Worst Case:** $$\Theta(n)$$if n is odd. See the tree below for an illustration of what happens in this case- hopefully the diagram will make it clearer as to why it's O(n).

![A diagram of what happens in the worst and best cases.](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M706TjXWj4GhSL0ddBD%2Fimage.png?alt=media\&token=7e051fad-b2d5-4a4e-b2b4-8c5f829f1f74)

![don't play with tnt, kids](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M7078yi4P91dbKtSXaB%2Fimage.png?alt=media\&token=63646f07-9a46-4871-ba32-d931efcd7fe8)
{% endtab %}
{% endtabs %}

## Challenge Problems

These problems are quite difficult. Don't be concerned if you don't feel confident in solving them (I certainly don't).

{% tabs %}
{% tab title="Question 7" %}
A huge disaster :ooo

```java
//initially start is 0, end is arr.length.
public int PNH(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    int counter = 0; 
    int result = 0;
    for (int i = start; i < end; i += 1) {
        if (arr[i] == 'a') {
            counter += 1;
        }
    }
    for (int i = 0; i < counter; i += 1) {
        result += PNH(arr, start + 1, end);
    }
    int mid = start + (end - start) / 2;
    return PNH(arr, start, mid) + PNH(arr, mid + 1, end);
}
```

{% endtab %}

{% tab title="Q7 Answer" %}
**Best Case:** $$\Theta(n\log(n))$$ If none of the characters in char\[] is 'a', then each call to PNH does $$\Theta(n)$$ work. Total work per layer is always N, with logN layers total.

**Worst Case:** $$\Theta(n!)$$ All of characters in char\[] is 'a'. In this case, the for loop recursive calls will dominate the runtime, because it'll be the main part of the recursive tree. The interval start to end is decreased by one in the for loop recursive calls, while that interval is halved in the return statement recursive calls. This means the return statement recursive calls will reach the base case in logn levels, while the recursive calls in the for loop will take n levels. Thus, we can proceed with the same analysis as question 4.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 8" %}
Congrats for making it this far! By now you should be an expert in asymptotic analysis :P Here's one last problem:

```java
//initially start is 0, end is arr.length.
public int lastOne(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    else if (arr[start] <= arr[end]) {
        return lastOne(arr, start + 1, end - 1);
    } else {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        return lastOne(arr, start + 1, end) 
        + lastOne(arr, start, end - 1) 
        + lastOne(arr, start + 1, end - 1);
    }
}
```

{% endtab %}

{% tab title="Q8 Answer" %}
**Best Case:** $$\Theta(n)$$ if the else if case is always true. This will produce a tree with height n/2, where each height does constant work.

**Worst Case:** $$\Theta(3^n)$$ if else if case is never true. Sorry no diagram yet :((
{% endtab %}
{% endtabs %}