Recurrence Relations and the Master Theorem · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Solving the cost of recursion

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

  1. Merge sort splits a list of n items into two halves, recursively sorts each half, and then merges the two sorted halves using about n comparison steps. Which recurrence describes its running time?

    • T(n) = 2T(n/2) + n
    • T(n) = T(n/2) + n
    • T(n) = 2T(n-1) + 1
    • T(n) = T(n-1) + n

  2. What does the equation T(n) = 2T(n/2) + n describe?

    • The number of variables in the program
    • The cost of a recursive method, written with its own smaller costs
    • The memory address of the next instruction

  3. Binary search checks the middle and continues in both halves.

    Circle one:   True   False

  4. Merge sort splits in half, sorts both halves, and merges in linear time. What is its recurrence?

    • T(n) = 2T(n/2) + n
    • T(n) = T(n/2) + n
    • T(n) = T(n/2) + 1

  5. The work outside the calls dominates the work in the leaves. Which master theorem case holds?

    • The third case
    • The first case
    • The second case

  6. For T(n) = 2T(n/2) + n, the master theorem compares n to n^(log base 2 of a) where a = 2 and b = 2. Which case applies and what is the result?

    • Case 1, T(n) = Θ(n)
    • Case 2, T(n) = Θ(n log n)
    • Case 3, T(n) = Θ(n squared)
    • None of the cases apply

  7. You draw the recursion tree for T(n) = 2T(n/2) + n. If the root does n work, how much work is done in total at the next level down (the two children)?

    • n
    • 2n
    • n/2
    • n squared

  8. When you expand a recurrence into a tree, what does one level stand for?

    • One line of source code
    • One variable in the program
    • One round of recursive calls

  9. A divide-and-conquer algorithm makes 4 recursive calls on half-size input and does n extra steps, giving T(n) = 4T(n/2) + n. What does the master theorem give?

    • Θ(n)
    • Θ(n log n)
    • Θ(n squared)
    • Θ(n squared log n)

  10. Leaf work dominates, but a student names the second case. What went wrong?

    • They expanded one level too few
    • They named the tie case although the leaves dominate
    • They wrote the recurrence with one call too many
LightMySky · lightmysky.comW1-mt_aOvLPV7rR8-s1

Answer key

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

Solving the cost of recursion W1-mt_aOvLPV7rR8-s1

  1. T(n) = 2T(n/2) + n · Each call makes two recursive calls on half-size input and does n merge steps, so T(n) = 2T(n/2) + n.
  2. The cost of a recursive method, written with its own smaller costs · A recurrence writes the cost on size n using the cost on smaller sizes.
  3. False · It keeps only one half, so the recurrence holds a single T(n/2).
  4. T(n) = 2T(n/2) + n · Two halves give 2T(n/2), and the linear merge adds n.
  5. The third case · Outside work on top means the third case, where the outside work dominates.
  6. Case 2, T(n) = Θ(n log n) · log base 2 of 2 is 1, so n^(log_b a) = n, which matches f(n) = n exactly. That is case 2, giving Θ(n log n).
  7. n · Each child solves a problem of size n/2 and does its own n/2 work, so two children do 2 times n/2, which is n.
  8. One round of recursive calls · Each level holds one round of calls, and the total is the sum of the levels.
  9. Θ(n squared) · Here a = 4 and b = 2, so n^(log_b a) = n^2. Since n grows polynomially slower than n^2, case 1 applies and T(n) = Θ(n^2).
  10. They named the tie case although the leaves dominate · Dominant leaves rule out a tie, so the first case was the right name.
Worksheet · LightMySky