| Inductive Equation | T(n) |
|---|---|
| T(n) = T(n-1) + bnk | O(nk+1) |
| T(n) = cT(n-1) + bnk, for c > 1 | O(cn) |
| T(n) = cT(n-1) + bdn, for c > 1 and c > d | O(cn) |
| T(n) = cT(n-1) + bdn, for c > 1 and d > c | O(dn) |
| T(n) = cT(n-1) + bdn, for c > 1 and c = d | O(ncn) |
| T(n) = aT(n/b) + f(n), for f(n) < nlogb a | O(nlogb a) |
| T(n) = aT(n/b) + f(n), for f(n) = nlogb a.logk n (k ≥ 0) | O(nlogb a.logk+1 n) |
| T(n) = aT(n/b) + f(n), for f(n) > nlogb a | O(f(n)) |
| Generating Function | Expansion |
|---|---|
| (1-x)-1 | 1 + x + x2 + x3 + x4 + x5 + ... |
| (1-x)-2 | 1 + 2x + 3x2 + 4x3 + 5x4 + 6x5 + ... |
| 2 * (1-x)-3 | 2 + 6x + 12x2 + 20x3 + 30x4 + 42x5 + ... |
| (1-x)-3 | 1 + 3x + 6x2 + 10x3 + 15x4 + 21x5 + ... |
| (1-x)-4 | 1 + 4x + 10x2 + 20x3 + 35x4 + 56x5 + ... |
| (1-2x)-1 | 1 + 2x + 4x2 + 8x3 + 16x4 + 32x5 + ... |
| (1-3x)-1 | 1 + 3x + 9x2 + 27x3 + 81x4 + 243x5 + ... |
| (1-x2)-1 | 1 + x2 + x4 + x6 + x8 + x10 + ... |
| (1-x3)-1 | 1 + x3 + x6 + x9 + x12 + x15 + ... |
| (1-2x2)-1 | 1 + 2x2 + 4x4 + 8x6 + 16x8 + 32x10 + ... |