问题描述:

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

相关阅读:
Top