In: Computer Science
Use the substitution method to prove the solutions for the following recurrences:
Recurrence |
Solution |
|
1 |
T(n) = T(n-1) + n |
O(n2) |
2 |
T(n) = T(n/2) + 1 |
O(lgn) |
3 |
T(n) = T(n/2) + n |
ϴ(nlgn) |
4 |
T(n) = 3T(n/2) + n |
O(nlg(3)). |
5 |
T(n) = 2T(n/2) + n2 |
O(n2) |
6 |
T(n) = 4T(n/2 + 2) + n |
O(n2) |
7 |
T(n) = 2T(n – 1) + 1 |
O(2n) |
8 |
T(n) = T(n – 1) + T(n/2) + n |
O(2n) |
9 |
T(n) = 4T(n/2) + cn. |
ϴ(n2) |