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?
Answer: A. π1(π)=Ξ(π2) β SolutionStep 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) =β¦
- A.
π1(π)=Ξ(π2)
- B.
π1(π)=Ξ(π2log2π)
- C.
π1(π)=Ξ(πlog45)
- D.
π1(π)=Ξ(πlog45 log2π)
Attempted by 105 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2