当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - What is time-complexity of T(N)=4T(N/2)+(N^2)/logN

问题描述:

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

分享给朋友:
您可能感兴趣的文章:
随机阅读: