Master Theorem
Preview this deck
if $$a > b^d$$
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
1
All-time users
2
Favorites
0
Last updated
4 years ago
Date created
Jan 27, 2021
Cards (4)
Master Theorem
(4 cards)
if $$a > b^d$$
$$T(n) \in \Theta(n^{\log_ab)$$
if $$a < b^d$$
$$T(n) \in \Theta(n^d)$$
if $$a = b^d$$
$$T(n) \in \Theta(n^d \log n)$$
What is the Master Theorem look like?
$$\begin{aligned} T(1) &= c \\ T(n) &= aT(n/b) + f(n) \end{aligned} $$
In order to find d, we need to find the highest power of $$f(n)$$