Counting Operations to Compare Algorithms · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Comparing algorithms by counting

Computing · Algorithms & Data Structures · ages 16-17
Name ______________________   Date ____________

  1. Binary search runs on a sorted list of 64 items. Roughly how many guesses in the worst case?

    • 64
    • 6 or 7
    • About 32

  2. Linear search runs on a list of 64 items and the target is last. How many comparisons does it make?

    Answer: ______________

  3. What does input size n mean?

    • The speed of the laptop
    • How many items it handles
    • The number of lines of code

  4. Why is a timed run weaker evidence than an operation count?

    • Counts run slower than timers
    • Counts ignore the machine
    • Timers cannot measure seconds

  5. A loop does 3 steps per item plus 7 setup steps on n items. Which formula gives its cost?

    • 3n + 7
    • 37n
    • n + 37

  6. Worst case analysis counts the fewest steps an algorithm could need.

    Circle one:   True   False

  7. A student counts only the best case and claims an algorithm is fast. What is the error?

    • Count the worst, not the best
    • Best case is always the largest count
    • Counting is useless in every case

  8. Two searches run on a list of a million items. Linear may need a million checks while binary needs about 20. Which grows faster and why?

    • Binary, because halving is expensive
    • Both grow equally
    • Linear tracks n; halving lags
LightMySky · lightmysky.comW1-mt_JkN961niFG-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Comparing algorithms by counting W1-mt_JkN961niFG-s1

  1. 6 or 7 · Each guess halves what is left, so a handful of guesses covers 64.
  2. 64 · One per item down the whole list makes 64.
  3. How many items it handles · n measures the input, such as the list length.
  4. Counts ignore the machine · Timing reflects the laptop; counting reflects the method.
  5. 3n + 7 · Work per pass times passes, plus setup, gives 3n + 7.
  6. False · Worst case counts the most steps over all inputs of size n.
  7. Count the worst, not the best · Only the worst case promises how bad things can get.
  8. Linear tracks n; halving lags · Linear work tracks n; halving adds about one guess per doubling.
Worksheet · LightMySky