For master's theorem T(n) = a*T(n/b) + f(n)
I am using 3 cases:
a*f(n/b) = c*f(n)
for some constant c > 1
then T(n) = (n^log(b) a)
a*f(n/b) = f(n)
then T(n) = (f(n) log(b) n)
a*f(n/b) = c*f(n)
for some constant c < 1
then T(n) = (f(n))
But when f(n) = log n
or n*log n
, the value of c
is dependent on value of n. How do I solve the recursive function using master's theorem?
Usually, f(n) must be polynomial for the master theorem to apply - it doesn't apply for all functions. However, there is a limited "fourth case" for the master theorem, which allows it to apply to polylogarithmic functions.
If f(n) = O(nlogba logk n), then T(n) = O(nlogba log k+1 n).
In other words, suppose you have T(n) = 2T (n/2) + n log n. f(n) isn't a polynomial, but f(n)=n log n, and k = 1. Therefore, T(n) = O(n log2 n)
See this handout for more information: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf