Senior LevelData Structures & Algorithms
How does the Master Theorem solve Divide-and-Conquer recurrences?
ā Interview Prompt: State the Master Theorem for T(N) = aT(N/b) + f(N) and solve recurrences for Merge Sort, Binary Search, and Strassen's algorithm.
The Master Theorem solves recurrences of the form:
$$T(N) = a \cdot T(N/b) + f(N)$$
where $a \geq 1$, $b > 1$, $f(N)$ is the work done outside recursive calls.
Three Cases (comparing $f(N)$ to $N^{\log_b a}$):
ā¢
Case 1: $f(N) = O(N^{\log_b a - \epsilon})$ ā $T(N) = \Theta(N^{\log_b a})$. (Recursive work dominates)
ā¢
Case 2: $f(N) = \Theta(N^{\log_b a})$ ā $T(N) = \Theta(N^{\log_b a} \log N)$. (Equal contribution)
ā¢
Case 3: $f(N) = \Omega(N^{\log_b a + \epsilon})$ ā $T(N) = \Theta(f(N))$. (Non-recursive work dominates)
Examples:
ā¢
Binary Search: $T(N) = T(N/2) + O(1)$ ā Case 1 ā $O(\log N)$.
ā¢
Merge Sort: $T(N) = 2T(N/2) + O(N)$ ā Case 2 ā $O(N \log N)$.
ā¢
Strassen's: $T(N) = 7T(N/2) + O(N^2)$ ā Case 1 ā $O(N^{\log_2 7}) \approx O(N^{2.81})$.
Code Implementation Example
markdown
Master Theorem Application Examples:
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāā
ā Algorithm ā Recurrence ā Result ā
āāāāāāāāāāāāāāāāāāā¼āāāāāāāāāāāāāāāāāāāāāā¼āāāāāāāāāāāāāāāāāāāāāā¤
ā Binary Search ā T(N)=T(N/2)+O(1) ā Case 1 ā O(log N) ā
ā Merge Sort ā T(N)=2T(N/2)+O(N) ā Case 2 ā O(N log N)ā
ā Quick Sort(avg) ā T(N)=2T(N/2)+O(N) ā Case 2 ā O(N log N)ā
ā Strassen's ā T(N)=7T(N/2)+O(NĀ²) ā Case 1 ā O(N^2.81) ā
ā Matrix Multiply ā T(N)=8T(N/2)+O(NĀ²) ā Case 2 ā O(NĀ³) ā
āāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāāš”Master Theorem cases applied to common divide-and-conquer algorithms.
šÆ Interview Key Takeaway
The Master Theorem is the primary tool for analysing D&C recurrences. Strassen's O(N^2.81) matrix multiply is the canonical Case 1 example beating naive O(NĀ³).
#DSA#Master Theorem#Recurrences#Complexity Analysis#Senior
Back to all Data Structures & Algorithms Questionsā