List of Recurrence Relations
Reading Time: 1 minute
Divide and Conquer Algorithms
| Algorithm | Recurrence Relation | Solution |
|---|---|---|
| Merge Sort | $$ T(n) = \begin{cases} Θ(1) & \text{if } n = 1 \\ 2T(n/2)+Θ(n) & \text{if } n > 1 \end{cases} $$ | $Θ(n \log_2 n)$ |
| Find Maximum Subarray | $$ T(n) = \begin{cases} Θ(1) & \text{if } n = 1 \\ 2T(n/2)+Θ(n) & \text{if } n > 1 \end{cases} $$ | $Θ(n \log_2 n)$ |
| Square Matrix Multiplication | $$ T(n) = \begin{cases} Θ(1) & \text{if } n = 1 \\ 8T(n/2)+Θ(n^2) & \text{if } n > 1 \end{cases} $$ | $Θ(n^3)$ |
| Strassen's Square Matrix Multiplication | $$ T(n) = \begin{cases} Θ(1) & \text{if } n = 1 \\ 7T(n/2)+Θ(n^2) & \text{if } n > 1 \end{cases} $$ | $Θ(n^{\log_2 7})$ |