Formula Sheets: Recurrence Relations

 Page 1


Recurrence Relations
T yp es of Recurrence Relations
Common F orms
• Linear: T(n) = T(n-1)+c , where c is a constan t.
• Divide-and-Conquer: T(n) = aT(n/b)+f(n) , where a= 1 , b > 1 .
• Sub tractiv e: T(n) = T(n-k)+c , where k and c are constan ts.
• Multi plicativ e: T(n) = aT(n/b)+cn
k
, where a,b,c,k are constan ts.
Solutions to Common Recurrence Relations
Iterativ e Metho d (Substitution)
• Linear: T(n) = T(n-1)+c? T(n) = O(n) .
• Linear with v ariable: T(n) = T(n-1)+n? T(n) = O(n
2
) .
• Line ar with logarithm: T(n) = T(n-1)+logn? T(n) = O(nlogn) .
• Subtrac tiv e: T(n) = T(n-k)+c? T(n) = O(n/k) .
• Multiplic ativ e: T(n) = 2T(n-1)+1? T(n) = O(2
n
) .
Recursion T ree Metho d
• F or T(n) = aT(n/b)+f(n) :
– Depth of tree: log
b
n .
– W ork p er lev el: a
i
·f(n/b
i
) at lev el i .
– T otal w ork: Sum of w ork across all lev els,
?
log
b
n-1
i=0
a
i
·f(n/b
i
) .
• Example: T(n) = 2T(n/2)+n? O(nlogn) .
Master Theore m
• F or T(n) = aT(n/b)+f(n) , where a= 1 , b > 1 :
– Case 1: If f(n) = O(n
log
b
a-?
) for ? > 0 , then T(n) = T(n
log
b
a
) .
– Case 2: If f(n) = T(n
log
b
a
log
k
n) , then T(n) = T(n
log
b
a
log
k+1
n) .
– Case 3: If f(n) = ?(n
log
b
a+?
) and af(n/b)= cf(n) for c < 1 , then T(n) = T(f(n)) .
• Example: T(n) = T(n/2)+1? O(logn) (Case 1).
• Example: T(n) = 2T(n/2)+n? O(nlogn) (Case 2).
Sp ecific Examples
Algorithm-Sp ecific Recur rences
• Binary Searc h: T(n) = T(n/2)+O(1)? O(logn) .
• Merge Sort: T(n) = 2T(n/2)+O(n)? O(nlogn) .
• Quic k Sort (a v erage): T(n) = 2T(n/2)+O(n)? O(nlogn) .
• Matrix Multiplication (Strassen’s): T(n) = 7T(n/2)+O(n
2
)? O(n
log
2
7
)˜ O(n
2.807
) .
1