C
C
CS61B Textbook
Search
⌃K
Comment on page

13.10 Exercises

Factual

  1. 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;
}
}
  1. 2.
    Let
    f(N)=2Nf(N) = 2N
    . Which of the following statements is true?
    • ​
      f(N)∈Θ(1)f(N) \in \Theta(1)
      ​
    • ​
      f(N)∈Θ(N)f(N) \in \Theta(N)
      ​
    • ​
      f(N)∈Θ(N2)f(N) \in \Theta(N^2)
      ​
    • ​
      f(N)∈O(1)f(N) \in O(1)
      ​
    • ​
      f(N)∈O(N)f(N) \in O(N)
      ​
    • ​
      f(N)∈O(N2)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
OO
 can be roughly thought of as "less than or equal to" some order of growth.
  • ​
    f(N)∈Θ(1)f(N) \in \Theta(1)
    ​
  • ​
    f(N)∈Θ(N)f(N) \in \Theta(N)
    ​
  • ​
    f(N)∈Θ(N2)f(N) \in \Theta(N^2)
    ​
  • ​
    f(N)∈O(1)f(N) \in O(1)
    ​
  • ​
    f(N)∈O(N)f(N) \in O(N)
    ​
  • ​
    f(N)∈O(N2)f(N) \in O(N^2)
    ​

Procedural

  1. 1.
    True or false. Suppose we have a function
    ff
    , and we are told
    f(N)∈Θ(N2)f(N) \in \Theta(N^2)
    . If we run
    ff
    on an input of size
    NN
    , then an input of size
    2N2N
    , it will take roughly 4 times as long.
  2. 2.
    True or false. Suppose we have a function
    ff
    , and we are told
    f(N)∈Θ(N2)f(N) \in \Theta(N^2)
    . If we run
    ff
    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

  1. 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.
​
Previous
13.9 Summary
Next
14. Disjoint Sets
Last modified 9mo ago