The Comparison-Sorting Lower Bound · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Why no comparing sort can beat n log n

Computing · Algorithms & Data Structures · ages 19-20
Name ______________________   Date ____________

  1. The n log n lower bound is a statement about every comparison sort, not only the ones people have written.

    Circle one:   True   False

  2. Three distinct items are sorted by comparisons. How many leaves does the decision tree need?

    • 6
    • 8
    • 4

  3. A binary decision tree has height 2. At most how many leaves can it hold?

    • 2
    • 4
    • 6

  4. A comparison sort handles 4 distinct items. How many leaves must its decision tree have?

    Answer: ______________

  5. Three items need 6 leaves but height 2 holds only 4. What follows?

    • Every input needs exactly 2 comparisons
    • The sort can skip comparing entirely
    • Some input forces at least 3 comparisons

  6. Mergesort runs in n log n time. What does matching the floor mean?

    • No comparison sort can beat it by more than a constant factor
    • It stops being a comparison sort
    • It wastes many extra comparisons

  7. You need exam marks from 0 to 100 sorted fast. What is the sensible move?

    • Give up because n log n blocks everything
    • Keep tuning one more comparing sort
    • Use the small value range with a non comparing method

  8. A classmate says counting sort proves the lower bound wrong. What is the error?

    • Counting sort compares pairs in secret
    • The bound never covered methods that read values instead of comparing
    • The bound only applies to three items
LightMySky · lightmysky.comW1-mt_7AfUsPV-jW-s1

Answer key

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

Why no comparing sort can beat n log n W1-mt_7AfUsPV-jW-s1

  1. True · It is a floor over all algorithms that play by comparing rules.
  2. 6 · Three items arrive in 6 orders, so the tree needs 6 leaves.
  3. 4 · Two levels of branches give at most 2 times 2 leaves.
  4. 24 · Four items arrive in 4 factorial orders, which is 24.
  5. Some input forces at least 3 comparisons · Six leaves do not fit in height 2, so the tree must grow taller.
  6. No comparison sort can beat it by more than a constant factor · The floor says no comparing method beats n log n, so mergesort is optimal there.
  7. Use the small value range with a non comparing method · The floor blocks comparing sorts only, and marks 0 to 100 allow value reading.
  8. The bound never covered methods that read values instead of comparing · Counting sort changes the rules, so the comparing floor does not apply to it.
Worksheet · LightMySky