algorithm - 如何找到函数的上界

Question

如何找到 f(n) = 2n^3-2n^2 的上限(大 O)。想知道C和n。

我在下面尝试过。

1. f(n)<=C*g(n)

2. 2n^3-2n^2 <= C*n^3

   我对寻找“C”的理解是，只考虑更高的多项式次数。所以..

3. 2n^3 <= C*n^3 ---> (省略2n^2)

4. 由此得出C的值为3。

但我书上给出的答案是C = 2。

问题1:请说明C怎么会是2。

问题2:如何求n的值。

Answer 1

你要证明的不等式是:

2n^3-2n^2 <= C*n^3 for all n >= n0.

实际上，任何 C >= 2 都有效。在这种情况下，n0 可以取任何值 >= 0。