# 13.10 Exercises

## Factual

1. 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;
}
}
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

## Procedural

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

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

Last updated