master-theorem - 应用主定理

Question

我正在尝试通过查看我的期中考试来准备考试。我不完全理解的一件事是主定理。我了解有三种情况，在这种情况下可以申请

T(n) = 25T(n/5) + n^(2)

但我的教授喜欢以这种形式给出一些

T(n) = {n+2 如果 n=0,1,2,3
T(n) = {4T(n-1) - 6T(n-2) + 4T(n-3) - T(n- 4) 否则

所以我很困惑是否有不同的方法来做主定理，或者我是否打算以某种方式将其更改为我理解的格式。

Answer 1

n^lg25=n^2。在非递归部分，我们有这个。所以我们应该 mult n^2 *log n。所以解决方案是 o(n^2 log n)