是的，O(n^2(是正确的。事实上，维基百科上关于主定理的文章中也有类似的例子。这个函数可以是任何东西，基本上你只需将递归树的深度和宽度与这个额外函数的成本进行比较，并检查是什么主导了复杂性。
我正在复习关于Big Oh运行时的期中测试。我遇到困难的一个问题是下面的重复，这个问题是关于大哦符号的。
T(n(=2T(n/2(+(2n^2+3n+5(
因此，通过使用主定理，其中k>log_b(a(，在这个问题中，我认为k是来自(2n^2(的2，a来自2T的2，并且b从(n/2(的2。因此，主定理的运行时间是当k>log_b(a(时，即2>log_2(2(=1，则T(n(=O(n^2(。
我的想法正确吗？我从来没有见过T(n(内部的二次运行时，但我相当确定它在这个问题中是O(n^2(。
感谢您的投入！