math - 为什么 an + b = O(n^2)？

Question

我需要使用 big-O 表示法的正式定义来证明 an + b = O(n ^{2 )。}我已经搜索了我拥有的几本关于离散数学的教科书以及几个在线资源，以查找与此证明相关的任何示例或定理，但没有好的结果。我不是在寻找直接的解决方案，而是寻找解决证明的正确方法或范式。

谁能指出我正确的方向？

Answer 1

这里有一个提示：如果 r ≤ s，n ^r ≤ n ^s对于所有 n ≥ 1。所以：

an + b ≤ an ² + bn ² = (a + b)n ²如果 n ≥ 1

从这里，你能看出当 n ≥ n _{0时你会选择 n 0}和 c 来证明 an + b ≤ cn ²吗？你能看到你如何也可以用它来证明 an + b = O(n) 吗？

希望这可以帮助！