algorithm - 下限：某种类型的输入大小 n 的算法所需的资源

Question

我被要求找到以下的下限：

T(n)= 23n^3-n^2-n。

所以这就是我如何进行的，我不知道我是否以正确的方式解决它：

T(n)>=c(23n^2-n^2) 对于所有大于 n>=n0 的 n

23n^3-n^2-n >=(22n^2) 对于所有 n>=2。

T(n)>=c|n^2| 对于所有 n>=2 c=22 n0=22。T(n) 在大欧米茄 n^2 中

请帮忙！

Answer 1

请注意，n^3 >= n^2对于n >= 1. 所以，-n^3 <= -n^2对于n >= 1.

请注意，n^3 >= n对于n >= 1. 所以，-n^2 <= -n对于n >= 1.

所以

23n^3 - n^2 - n >= 23n^3 - n^3 - n^3 = 21n^3.

因此，21n^3是一个不错的下限。

直观地说，这是有道理的，因为它本质上是立方的，因此应该有一些23n^3 - n^2 - n的下限和上限（下限与上限不同）。cn^3ccc