algorithmmathrecurrencemaster-theorem

Solving 4T(n/5) + log5(n * sqrt(n)) with the master theorem

I'm trying to solve the recursion 4T(n/5) + log5(n * sqrt(n)) with the master theorem but I've run into some difficulties.

I understand using the form T(n) = a T(n/b) + theta(n^k log^p n) would yield:

a = 4
b = 5
k = 0

but how would I deal with the n * sqrt n within the log? I cannot understand how to proceed. Thanks

Solution

  • log(n * sqrt(n)) = log(n^{1.5}) = 1.5* log(n)

    thus your formula becomes T(n) = 4T(n/5) + 1.5 * log5(n)