大 O 表示法和多项式

Question

所以我有这个问题要做，我真的不确定从哪里开始：

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

1. T（n） = 2n + 3 ∈ O（n）
2. T（n） = 5n + 1 ∈ O（n²）
3. T（n） = 4n 2 + 2n + 3 ∈ O（n²）

如果有人能指出我正确的方向（你不一定必须给我确切的答案），我将不胜感激。

Answer 1

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

如果 a ≤ b，

则对于任何 n ≥ 1，n^a ≤ n^b。

例如，以下是处理其中第一个的方法：如果 n ≥ 1，则 2n + 3 ≤ 2n + 3n = 5n。 因此，如果你取 n 0 = 1 和 c = 5，则对于任何 n ≥ n₀ 的 2n + 3 ≤ 5n，你就会得到这个数字。 因此，2n + 3 = O（n）。

尝试使用类似的方法来解决其他问题。 对于第二个问题，您可能希望使用它两次 - 一次是使用某个线性函数的上限 5n + 1，一次是使用某个二次函数的上界线性函数。

希望这有帮助！