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

user_12162514 0
Viewed 288

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

master-theorem recurrence math algorithm
1 Answers

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)

user_127503530
Related