13.10 Exercises


  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


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!


  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