In Simple Words: Solves divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$: - Compare $f(n)$ against $n^{\log_b a}$: 1. If work at leaves dominates ($f(n) < n^{\log_b a}$): $T(n) = \Theta(n^{\log_b a})$. 2. If work is evenly distr...

Q3: The Master Theorem. - DSA Patterns (Multi-Lang)

In Simple Words: Solves divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$:

Compare $f(n)$ against $n^{\log_b a}$:

If work at leaves dominates ($f(n) < n^{\log_b a}$): $T(n) = \Theta(n^{\log_b a})$.
If work is evenly distributed ($f(n) = n^{\log_b a} \log^k n$): $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. E.g., Merge Sort: $T(n) = 2T(n/2) + O(n) \implies O(n \log n)$.
If work at root dominates ($f(n) > n^{\log_b a}$): $T(n) = \Theta(f(n))$.

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def merge_sort(arr: list[int]) -> list[int]:
    # T(n) = 2T(n/2) + O(n) -> O(N log N) by Master Theorem Case 2
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Merge step: O(n)
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res