Back to the 2023 paper

Module 1: Introduction

20237m

Consider the following recurrence relation:
T(n)=2T(n/2)+nT(n) = 2T(n/2) + n
Use the substitution method to find an asymptotic upper bound for the function T(n)T(n).

Worked SolutionAI Assisted

T(n)=2T(n/2)+nT(n)=2T(n/2)+n — Substitution Method, Upper Bound O(nlog⁡n)O(n \log n)

Guess: T(n)≤c nlog⁡nT(n) \le c\, n \log n for some c>0c>0, n≥n0n\ge n_0 (with T(1)=Θ(1)T(1)=\Theta(1)).

Inductive Hypothesis: Assume for n/2n/2: T(n/2)≤c(n/2)log⁡(n/2)T(n/2) \le c (n/2) \log(n/2).

Inductive Step:
T(n)=2T(n/2)+n≤2[cn2log⁡n2]+n=cn(log⁡n−log⁡2)+n=cnlog⁡n−cnlog⁡2+n \begin{aligned} T(n) &= 2T(n/2)+n \\ &\le 2\left[ c\frac{n}{2}\log\frac{n}{2}\right]+n \\ &= c n (\log n - \log 2)+n \\ &= c n \log n - c n \log 2 + n \end{aligned}
With log⁡\log base 2, log⁡2=1\log 2=1:
T(n)≤cnlog⁡n−cn+n=cnlog⁡n−(c−1)nT(n) \le c n \log n -c n + n = c n \log n -(c-1)n
Choose c≥1c \ge 1 → −(c−1)n≤0-(c-1)n \le 0 → T(n)≤cnlog⁡nT(n) \le c n \log n.

Base case: Need T(1)≤c⋅1⋅log⁡1=0T(1) \le c\cdot1\cdot\log1 =0 fails for log base2. Use T(2)T(2) or define T(1)=1T(1)=1, choose n0=2n_0=2, pick cc large enough: c⋅2log⁡2≥T(2)=2T(1)+2=4c\cdot2\log2 \ge T(2)=2T(1)+2=4 → c≥2c\ge2 works. More formally prove for n≥2n\ge2, or use nlog⁡nn\log n with T(1)=Θ(1)T(1)=\Theta(1) and show T(n)≤cnlog⁡n+bT(n)\le c n\log n +b variant.

Hence T(n)=O(nlog⁡n)T(n)=O(n\log n).

Tight bound: Similarly show T(n)≥c′nlog⁡nT(n) \ge c' n\log n → Ω(nlog⁡n)\Omega(n\log n) → Θ(nlog⁡n)\Theta(n\log n).
By Master Theorem case 2 (a=2a=2, b=2b=2, nlog⁡ba=n1n^{\log_b a}=n^1, f(n)=n=Θ(nlog⁡ba)f(n)=n=\Theta(n^{\log_b a})) → T(n)=Θ(nlog⁡n)T(n)=\Theta(n\log n).

Application: This is the Merge Sort recurrence.

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.