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