retagged by
470 views
3 votes
3 votes
$T(N) = T(N/4) + T(N/2) + N^{2}$

Find Order of given Reccurence??
retagged by

1 Answer

Best answer
6 votes
6 votes

This question is solved conveniently using recursion tree method .For that we need to know the number of levels of the recursion tree and the cost of function calls at each level.

The cost is determined by f(n) which is n2 in this case corresponding to T(n).

Now the cost for T(n)  =   n2

 So cost for       T(n/2)  =  (n/2)  =   n2 / 4

                        T(n/4)  =  (n/4)2  = n2 / 16

So total cost at 2nd level =  n2/4 + n2/16  =   5n2 / 16

So cost has decreased from first level , hence it is a series of decreasing G.P. .Hence 

Total cost =  n2 [ 1 + 5/16 + (5/16)2 + ...]

               = kn2 for some constant k [ Since it is a decreasing G.P. the sum of the terms within the brackets will result in some constant value  , say  k]

               =  O(n2)

Now we have 2 other cases :

a) Had the cost at each level were increased from 1st level to subsequent bottom levels , then we need to find the value of actual series.

b) Had the cost at each level were remain same as in the case of mergesort then we would simply multiply the cost of function calls in each level with the number of levels in the recursion tree.

selected by

Related questions

2 votes
2 votes
1 answer
1
Deepak Yadav asked Jan 6, 2017
431 views
Solve this problem?
1 votes
1 votes
1 answer
2
Rajesh Pradhan asked Oct 14, 2016
1,615 views
On which of the following recurrence relation Master Theorem cannot be applied?A. T(n)=2T(n/2)+nlognB. T(n)=T(n/2)+1C. T(n)=8T(n/2)+lognD. T(n)=7T(n/4)+n2I think we can a...
1 votes
1 votes
0 answers
3
Abhijeet_Kumar asked Dec 28, 2017
160 views
0 votes
0 votes
1 answer
4
Smriti012 asked Feb 3, 2017
685 views
Best algorithm for this set:1.Independently sorting each of 1,000,000 arrays, each with 5 elements.2.Sorting a set of 4,000,000 numbers in worst case O(n lg n) time.