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

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.