How do I Solve this ?
T(n) = T(n/4) + T(3n/4) + cn
Ans is \theta(nLogn)
How this answer can be achieved using master theorem or any other effecient method?
The recursion tree for the given recursion will look like this:
Size Cost
n n
/ \
n/4 3n/4 n
/ \ / \
n/16 3n/16 3n/16 9n/16 n
and so on till size of input becomes 1
The longes simple path from root to a leaf would be n-> 3n/4 -> (3/4) ^2 n .. till 1
Therefore let us assume the height of tree = k
((3/4) ^ k )*n = 1 meaning k = log to the base 4/3 of n
In worst case we expect that every level gives a cost of n and hence
Total Cost = n * (log to the base 4/3 of n)
However we must keep one thing in mind that ,our tree is not complete and therefore
some levels near the bottom would be partially complete.
But in asymptotic analysis we ignore such intricate details.
Hence in worst Case Cost = n * (log to the base 4/3 of n)
which is O( n * log n )
Now, let us verify this using substitution method:
T(n) = O( n * log n) iff T(n) < = dnlog(n) for some d>0
Assuming this to be true:
T(n) = T(n/4) + T(3n/4) + n
<= d(n/4)log(n/4) + d(3n/4)log(3n/4) + n
= d*n/4(log n - log 4 ) + d*3n/4(log n - log 4/3) + n
= dnlog n - d(n/4)log 4 - d(3n/4)log 4/3 + n
= dnlog n - dn( 1/4(log 4) - 3/4(log 4/3)) + n
<= dnlog n
as long as d >= 1/( 1/4(log 4) - 3/4(log 4/3) )