AppliedMultiple choiceFree solution

What does the recurrence T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) solve to?

  1. AΘ(n)\Theta(n)
  2. BΘ(nlog⁡n)\Theta(n\log n)
  3. CΘ(n2)\Theta(n^2)
  4. DΘ(log⁡n)\Theta(\log n)
Show the answer and worked solution

Answer: B – Θ(nlog⁡n)\Theta(n\log n)

Draw the recursion tree. Each level does O(n)O(n) work in total and there are log⁡2n\log_2 n levels, so the answer is Θ(nlog⁡n)\Theta(n\log n). In master-theorem terms this is the tied case, f(n)=Θ(nlog⁡ba)f(n) = \Theta(n^{\log_b a}) with a=b=2a = b = 2 and d=1d = 1. It is merge sort, and recognising it on sight is worth more than re-deriving it. Changing aa to 33 would tip it into the leaf-dominated case and give Θ(nlog⁡23)\Theta(n^{\log_2 3}), so the comparison between aa and bdb^d is the whole test.

Worked solution

  1. Formula
    T(n)=aT(n/b)+ndT(n) = aT(n/b) + n^{d}
  2. Substitute
    a=2, b=2, d=1a = 2, \ b = 2, \ d = 1
  3. Solve
    a=bd=2a = b^{d} = 2
    The tied case.
  4. ⇒Θ(ndlog⁡n)=Θ(nlog⁡n)\Rightarrow \Theta(n^{d}\log n) = \Theta(n\log n)
  5. a=3⇒Θ(nlog⁡23)a = 3 \Rightarrow \Theta(n^{\log_2 3})
    One extra subproblem changes the class.
  6. Answer
    Θ(nlog⁡n)\Theta(n\log n)

Sanity check. Each of the lognlog n levels does O(n)O(n) work in total, which is the recursion tree drawn in one line.

  • A. The linear work happens at every one of log⁡n\log n levels.
  • B. Correct – f(n)=Θ(nlog⁡ba)f(n) = \Theta(n^{\log_b a}), so the tied case applies. This is merge sort.
  • C. That would need the work outside the calls to be quadratic.
  • D. That is the binary-search recurrence, with one subproblem and constant work.

Takeaway: Recognise T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) on sight.

Answer it in practice – your answer is marked and recorded.

Reported in interviews at

Optiver, Hudson River Trading, Jump Trading

More data structures and algorithms questions

What does the recurrence T(n) = 2T(n/2)+O(n) solve to? · QuantMax