证明以下关于渐近符号的问题的正确方法是什么？

Question

我必须证明 f(n)= 5n+2=O(n^2) 而且我知道 O(n) 是真的，所以很明显，对于更高的 n 来说它也是真的但是如何证明呢？

Answer 1

好的。这是证明这一点的简单方法。我把它包括在这里，希望它对其他有类似问题的人有用

5n + 2 <= 5n + 2n         ; n >= 1
        = 7n              ; always
       <= n*n             ; n >= 7
        = n^2             ; always

因此，存在一个常量 c，在本例中为 c=1，以及一个整数 N，在本例中为 N=7，使得

5n + 2 <= c*n^2         for all n >= N

那么，根据定义

5n + 2 = O(n^2).

还要注意前两行

5n + 2 <= 5n + 2n         ; n >= 1
        = 7n              ; always

足以说明5n + 2 = O(n)。在这种情况下，c=7 和 N=1.

What is the proper way to prove the following question on asymptotic notation?