> 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/13.-asymptotics-i/13.10-exercises.md).

# 13.10 Exercises

## Factual

1. Analyze the runtime of the following code in terms of `N`:

```java
for (int i = 0; i < N; i++) {
    int j = 0;
    while (j < N) {
        j = N;
    }
}
```

2. Let $$f(N) = 2N$$. Which of the following statements is true?
   * [ ] $$f(N) \in \Theta(1)$$
   * [ ] $$f(N) \in \Theta(N)$$
   * [ ] $$f(N) \in \Theta(N^2)$$
   * [ ] $$f(N) \in O(1)$$
   * [ ] $$f(N) \in O(N)$$
   * [ ] $$f(N) \in O(N^2)$$

<details>

<summary>Problem 1</summary>

Note that the inner loop only runs once, since it immediately sets `j = N` in the first iteration. As such, the runtime is just the runtime of the outer loop, which iterates `N` times. The overall runtime, then, is linear.

</details>

<details>

<summary>Problem 2</summary>

Remember that $$\Theta$$ means the same order of growth (linear), while $$O$$ can be roughly thought of as "less than or equal to" some order of growth.

* [ ] $$f(N) \in \Theta(1)$$
* [x] $$f(N) \in \Theta(N)$$
* [ ] $$f(N) \in \Theta(N^2)$$
* [ ] $$f(N) \in O(1)$$
* [x] $$f(N) \in O(N)$$
* [x] $$f(N) \in O(N^2)$$

</details>

## Procedural

1. **True or false.** Suppose we have a function $$f$$, and we are told $$f(N) \in \Theta(N^2)$$. If we run $$f$$on an input of size $$N$$, then an input of size $$2N$$, it will take roughly 4 times as long.
2. **True or false.** Suppose we have a function $$f$$, and we are told $$f(N) \in \Theta(N^2)$$. If we run $$f$$on an input of size 100, then an input of size 200, it will take roughly 4 times as long.

<details>

<summary>Problem 1</summary>

**True**. This is the definition of asymptotics.

</details>

<details>

<summary>Problem 2</summary>

**False**. 100 may be too small of an input for asymptotic behavior to start displaying. Remember that asymptotics only apply to very large inputs!

</details>

## Metacognitive

1. Why do use asymptotics instead of empirical timing (for example, like the `Stopwatch` class from Lab 3)?

<details>

<summary>Problem 1</summary>

There are several advantages to using asymptotics over empirical timing. See if you can come up with more beyond the list below!

* Different computers run at different speeds. Depending on architecture, hardware components, even room temperature, the same code can execute with vastly different empirical times.
* It may not be feasible to test code on extremely large inputs.&#x20;
* Asymptotics are language-agnostic. The same algorithm may have different empirical runtime depending on which language it's written in (for example, C is usually around 10-400x faster than Python), but will have the same asymptotic runtime.
* The worst-case runtime may only occur in certain cases that are hard to measure empirically.&#x20;

</details>