Докажите, что 5nˆ2 + 2n - 1 есть O (nˆ2) при n> = 1

Question

Упражнение: Докажите, что 5nˆ2 + 2n - 1 равно O (nˆ2) для n> = 1

Вот что я сделал:

1. 5nˆ2 + 2n - 1 <5nˆ2 + 2n. </li>
2. 5nˆ2 - 1 <5nˆ2 </li>

это означает, что C = 5 и n0 = 1

Я немного нервничаю, потому что чувствую, что это слишком простая процедура. Я сделал что-то не так или это хорошо?

Спасибо!

Answer 1

Прежде всего, большое обозначение O относится к асимптотическому росту, поэтому n >= 1 фактически избыточно.
По определению большого O, f(n) = O(g(n)), если существует какое-то c, n0 > 0 stдля всех n > n0 он содержит f(n) <= cg(n).
Так что в нашем случае: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 как и для любого натурального целого числа, он гласит, что n^2 >= n.
Выберите c = 7, n0 = 1 и для всех n > n0 мы получимчто 5n^2 + 2n -1 <= 7n^2 = cn^2.
Сотрясение: 5n^2 + 2n - 1 = O(n^2).