Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
5 Cards in this Set
- Front
- Back
|
Master Theorem works for recurrences that can be transformed to the following type: |
T(n) = aT(n/b) + f(n) |
|
|
First Case: f(n) = O(n^c) where c < Logb(a) |
T(n) = O(n^Logb(a)) |
|
|
If f(n) = O(n^c) where c = Logb(a) |
T(n) = O(n^c Log(n)) |
|
|
If f(n) = O(n^c) where c > Logb(a) |
T(n) = O(f(n)) |
|
|
Case 2 can be extended to f(n) = O(n^c Log^k(n)) If f(n) = O(n^c Log^k(n)) for some constant k >= 0 and c = Logb(a) |
T(n) = O(n^c Log^(k+1)(n) |
