Как правильно доказать следующий вопрос об асимптотической записи?

Question

Я должен доказать, что f (n) = 5n + 2 = O (n ^ 2), и я знаю, что это верно для O (n), поэтому очевидно, что это будет верно для более высокой степени n, но как доказать это?

Answer 1

OK. Вот простой способ доказать это. Я включил это здесь в надежде, что это могло бы быть полезным для других с подобными проблемами

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.