A recurrence relation is an equation in which each term of the sequence is defined as a function of the preceding terms.
There are different ways of solving these relations, we're going to examine:
The premise for this type of solution is to continually substitute the recurrence relation on the right hand side (ie. substitute a value into the original equation and then derive a previous version of the equation). The various derivations should lead to a generalized form of the equation that can be solved for a time constraint on the algorithm/equation: For example:
T(n) = T(n/2) + c
The only substitution available at this point is to substitute n/2 for n in the original equation:
T(n/2) = T(n/2/2) + c T(n/2) = T(n/4) + c
Add c to both sides to derive the original equation:
T(n/2) + c = T(n/4) + c + c
Therefore:
T(n) = T(n/2) + c = T(n/4) + c + c
Now that another equation has been derived there is a new substitution that can be made in the original: n/4 for n
T(n/4) = T(n/4/2) + c T(n/4) = T(n/8) + c T(n/4) + c + c = T(n/8) + c + c + c
T(n) = T(n/2) + c = T(n/4) + c + c = T(n/8) + c + c + c
In general, the basic equation is:
T(n) = T(n/2k) + kc for k > 0
Making an assumption that n = 2k allows for:
T(n) = T(n/2k) + kc T(n) = T(n/n) + (log n) * c T(n) = T(1) + c log n T(n) = b + c log n T(n) = O(log n)
The premise for this type of solution is to substitute values for n, add up the results, and eliminate like terms. For example:
T(n) = T(n/2) + c T(n/2) = T(n/4) + c T(n/4) = T(n/8) + c T(n/8) = T(n/16) + c ... T(n/2k-1) = T(n/2k) + c T(n) + T(n/2) + T(n/4) + T(n/8) + ... + T(2) = T(n/2) + c + T(n/4) + c + T(n/8) + c + T(n/16) + c + ... + T(2k) + c T(n) = T(n/2k) + kc
Making an assumption that n = 2k allows for:
T(n) = T(n/2k) + kc T(n) = T(n/n) + (log n) * c T(n) = T(1) + c log n T(n) = b + c log n T(n) = O(log n)
The Basic Series:
S(n) = 1 + 2 + 3 + 4 + ... + n n = ∑ i i=1 = n( 1 + n ) 2
Sum of Squares:
n S(n) = ∑ i2 i=1 = n(n + 1)(2n1 + 1) 6 ≈ n3 for large n 3
Sum of Exponents:
n S(n) = ∑ ik i=1 nk+1 = _____ for large n and k ≠ -1 |k+1|
Geometric Series:
n S(n) = ∑ Ai i=0 An+1 - 1 = --------- A - 1 Special Case: A = 2 results in 2n+1 - 1
You may assume that n = 2k:
T(1) = 1 T(n) = 2T(n/2) + n