Asymptotic lower/upper bounds for T(n) [Master Theorem?]
I am trying to find out how to solve the lower/upper bounds for a given T(n) - the book I have been reading refers to using the Master Theorem which I seem to be able to apply in the standard case, however when the T(n) is non-standard I am at a loss to see how to solve the problem.
For example, with T(n) = 3T(n/2) + n^1/2 I know that a=3, b=2, k=1/2 so T(n) = O (n^log1.58) (using the standard Master Theorem approach).
But now I am looking into solving the following problem:
T(n) = 5T(n/5) + nlogn
In this case f(n) = n*log(n) (not of the form n^k) and I am not sure how to evaluate this using either the Master Theorem (or any other valid method) - somehow I need to determine if
Anyone have any clues?
Any help would be much appreciated.