How to solve T(n)=T(n/4)+T(3n/4)+nlogn

Viewed 866

I have got a question of solving this recursive complexity T(n)=T(n/4)+T(3n/4)+nlogn. Can you help me to solve it?

2 Answers

You can use Akra-Bazzi method with the following paramters:

a_1 = a_2 = 1, 
b_1 = 1/4, b_2 = 3/4
p = 1

T(n) = \Theta(n * (1 + integral( u log(u)/ u^2 du,1, n))) = 
       \Theta(n * (1 + (log^2(n)/2))) = 
       \Theta(n log^2(n))

Notice that 3n/4 > n/4. Hence we can see that T(n) <= 2T(3n/4) + n log n.

Now we can apply Master Theorem. We can see that a=2, b=4/3 and f(n) = n log n

We can see that, log_(4/3) 2 = 2.41

Hence n^log_b a >= f(n).

Thus by Master's theorem, we have T(n) = O(n^2.41)

Related