Asymptotic lower/upper bounds for T(n) [Master Theorem?]

[Shaitan00]

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.
Thanks,

 

[lippyka]

In this case, you can use the Akra–Bazzi theorem to find the upper and lower bounds. The Akra–Bazzi theorem states that if T(n) is of the form aT(n/b)+f(n), where a and b are constants and f(n) is a function such that f(n)=O(nlogbn) for all sufficiently large n, then T(n)=Θ(nlogbn). Therefore, in your example, since f(n)=nlogn, we can conclude that T(n)=Θ(nlog5n).