我对算法和时间复杂性非常陌生，正在读一本书。根据我对Big-Oh函数的了解，对于任何f（n）都不是唯一的，取决于常数c和n0。我的第一个疑问是Master定理是否给出了Big Oh函数的最佳情况。我的第二个疑问-可能很愚蠢-在解决问题1和2之后，我试图继续前进并验证答案，却感到困惑。
现在我的尝试如下： 1）cn2≥3T（n / 2）+n2⇒kn2≥T（n / 2） ⇒k''（n / 2）2≥T（n / 2），因此与O（n2）一致。 为什么对概率2来说不一样，即为什么不是O（n2）而是O（n2logn）？我想它背后有一些数学运算，我想知道（如果我到目前为止有足够的背景知识）。
Depending on your conditions, Masters theorem gives either the worst-case time complexity
Big-Oor a tight boundBig-ThetaNow the actual proof of Master's theorem involves drawing the recurrence tree and some approximations using the geometric series progression. Here's a link to a pdf containing the process.