Consider the following recurrence relations: For all 𝑛>1, 𝑇1(𝑛) = 4𝑇1(𝑛 /…
2026
Consider the following recurrence relations:
For all 𝑛>1,
𝑇1(𝑛) = 4𝑇1(𝑛 / 2) + 𝑇2(𝑛)
𝑇2(𝑛) = 5𝑇2(𝑛 / 4) + Θ(log2𝑛)
Assume that for all 𝑛≤ 1,𝑇1(𝑛) =1 and 𝑇2(𝑛) = 1.
Which one of the following options is correct?
- A.
𝑇1(𝑛)=Θ(𝑛2)
- B.
𝑇1(𝑛)=Θ(𝑛2log2𝑛)
- C.
𝑇1(𝑛)=Θ(𝑛log45)
- D.
𝑇1(𝑛)=Θ(𝑛log45 log2𝑛)
Attempted by 60 students.
Show answer & explanation
Correct answer: A
Solution
Step 1: Analyze T2(n). Using Master Theorem with a=5, b=4, we get Theta(n^log4 5).
Step 2: Substitute into T1(n). The recurrence becomes T1(n) = 4T1(n/2) + Theta(n^log4 5).
Step 3: Apply Master Theorem again. Here a=4, b=2, so log_b a = 2.
Step 4: Compare n^log4 5 with n^2. Since 2 > log4 5, the n^2 term dominates.