问题描述:

This question was given in MIT video on analysis of algorithms,

The following question can not be done using master method and can be solved using recurrence tree.

Can any please tell me the solution?

Why exactly do you claim that it can not be done with the masters theorem?. This theorem has only some constraints that `a`

and `b`

are constants and `a >= 1`

and `b > 1`

. It will hold for any `f(n)`

and therefore you can apply it here.

If you will apply it you would see that `a=4, b=2`

and therefore `c = 2`

. `n^c`

grows faster than your `f(n)`

and therefore the complexity is `O(n^2)`

.