algorithm - 通过给出一个紧界来求解递归 T(n) = T(n/3) + O(logn) + n

Question

在解决重复问题时可以放弃较低的术语吗，就像在这种情况下我决定放弃 O(logn).

写得不好请见谅！这是我解决重复问题的尝试：

Answer 1

O(log n) + n = Theta(n)您可以使用 Master Theorem重写并继续您愉快的方式来获得Theta(n).

如果您想要一个更好的界限，您可以使用替换方法来验证T(n) = 3n/2 + c log^2 n某个固定常数。c