Regularity condition in the master theorem.
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
1
2
3
aT(n/b) + f(n)
Case 1
T(n)=2T(n/2)+1
T(n) ------(1) / \ T(n/2) T(n/2) ------(2) / \ / \
Case 2
T(n)=2T(n/2)+n
T(n) ------(n) / \ T(n/2) T(n/2) ------(n) / \ / \
Case 3
T(n)=T(n/2)+n
T(n) ------(n) | T(n/2) ------(n/2) |
regulatory condition
af(n/b)<=cf(n).
T(n) = T(n/2) + n(sin(n – /2) + 2)