Théorème maître

Pour $T(n) = a\, T(n / b) + \Theta(n^d)$ avec $a \ge 1$, $b > 1$ : si $d > \log_b\, a$, $T(n) = \Theta(n^d)$ ; si $d = \log_b\, a$, $T(n) = \Theta(n^d \log n)$ ; si $d < \log_b\, a$, $T(n) = \Theta(n^{\log_b\, a})$. Pour le tri fusion, $a = 2$, $b = 2$, $d = 1 = \log_2 2$ : $\Theta(n \log n)$.