CS61B

13.10 Exercises

Factual

Analyze the runtime of the following code in terms of N:

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

Let $f(N) = 2N$ $f (N) = 2 N$ . 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)$

Problem 1

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.

Problem 2

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

Procedural

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

Problem 1

True. This is the definition of asymptotics.

Problem 2

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

Metacognitive

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

Problem 1

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