Как доказать, используя big-O

Question

У меня сейчас проблема с большой нотацией. У меня есть следующий вопрос, который я пытаюсь выяснить.

В настоящее время у меня есть формула: T (n) есть O (f (n)), и я должен использовать это, чтобы доказать непосредственно из определения большого O, что 3n ^ 2 + 11n + 6 есть O (n ^ 2) .

Мне было интересно, может ли кто-нибудь помочь мне разобраться в этой проблеме, так как у меня возникают проблемы при ее решении.

Answer 1

Я думаю, что это может помочь: Для n≥k существует константа, назовем ее "c", которая удовлетворяет условию 3n ^ 2 + 11n + 6 ≤ c ∗ n ^ 2. Допустим, мы выбрали k = 1. Мы знаем, что n ^ 2 ≥ n ^ 2 ≥ n ≥ 1

Итак:
3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2

Теперь пусть с = 20. => сложность O (n2).