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?
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?
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)