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

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。