algorithm - Big-O 表示法和多项式？

Question

所以我有这个问题要做，但我不太确定从哪里开始:

使用 Big-O 的定义，证明以下内容:

1. T(n) = 2n + 3 ∈ O(n)
2. T(n) = 5n + 1 ∈ O(n²)
3. T(n) = 4n² + 2n + 3 ∈ O(n²)

如果有人能指出我正确的方向(您不一定需要给我确切的答案)，我将不胜感激。

Answer 1

您可以使用相同的技巧来解决所有这些问题。作为提示，请使用以下事实

If a ≤ b, then for any n ≥ 1, n^a ≤ n^b.

作为示例，您可以通过以下方式实现第一个:如果 n ≥ 1，则 2n + 3 ≤ 2n + 3n = 5n。因此，如果取 n₀ = 1 且 c = 5，则对于任何 n ≥ n₀ ，2n + 3 ≤ 5n。因此，2n + 3 = O(n)。

尝试使用类似的方法来解决其他问题。对于第二个问题，您可能需要使用它两次 - 一次使用某个线性函数来设置 5n + 1 的上限，再一次使用一些二次函数来设置该线性函数的上限。

希望这有帮助!