面临减法时的算法复杂性

我必须简化以下公式才能获得算法的时间复杂度：(n^2-n)/3。是否有任何适用的规则可以让我进一步简化这个表达式为更“常见”的 θ(n^2) 或类似的东西（我假设这就是结果，可能是错误的）。

我根本不知道如何处理这里的减法。通常，如果两个值相加，您只考虑最高的那个来分析算法的复杂性。这种情况我该怎么办？

Since Θ is a 紧束缚，没有更好的简化，如果某些函数f(n)都在Θ(h(n)) AND in Θ(g(n))代表着Θ(h(n)) = Θ(g(n))，因此对于任何其他函数，您会发现，信息增益超过Θ(n^2)在你的例子中没有。

在处理减法时n^k - n^m, where k>m，你可以简单地“扔”n^m在分析大 θ 表示法时。

这是真的，因为：

n^k - n^m <= n^k  
-> and thus it is in O(n^k)

另一方面：
对于每一个m,k有一定的价值N这样对于所有n>N: 0.5n^k >= n^m， 因此：

n^k - n^m >= n^k - 0.5n^k = 0.5n^k    for n > N
-> it is also in Omega(n^k)

既然我们找到了上限和下限，我们可以得出结论n^k-n^m, when k>m, is in Θ(n^k).
（对于处于不同 θ 复杂度类别的一般 f(n),g(n) 可以进行类似的证明）。