Тета нотация доказательство функции

Question

f (n) = 4n² + 3n - 5 = Theta (n²)

Как я могу это доказать?Согласно моим исследованиям, эта запись должна быть такой:

для положительных констант c1, c2 и n0 таких, что c1 * g (n) <= f (n) <= c2 * g (n) для всех n> = n0 но я не смог сделать.

Answer 1

У нас есть f(n) = 4n² + 3n - 5.

---

Претензия 1: f(n) <= 5n² for all n

У нас 5n² - f(n) = n² - 3n + 5 = (n - 3/2)² + (11/4) > 0 для всех n.

Претензия 2: 4n² <= f(n) for n >= 2

У нас есть f(n) - 4n² = 3n - 5 >= 0 для n >= 5/3 >= 2.

---

Из вышеизложенного мы имеем 4n² <= f(n) <= 5n² для n >= 2.

Сравните с большим тэта-определением c1 * g(n) <= f(n) <= c2 * g(n) для всех n >= n0.

У нас есть c1 = 4, c2 = 5, g(n) = n² и n0 = 2.

Answer 2

4n² будет расти быстрее, чем 3n² и медленнее, чем 5n².Остается выяснить, к какому n значению относятся неравенства.

На графике будет работать n0 = 2.

Выможет показать это более формально, но параболы не могут лгать.

Answer 3

Первый шаг, давайте заполним уравнение и посмотрим, что нам нужно доказать.

c1 * n² <= 4n² + 3n - 5 <= c2 * n² (for n >= n0)

Я докажу половину этого, а остаток оставлю вам.

Предположим

c1 = 3 (since it makes sense that 3n² <= 4n² for n >= n0)

Нам нужно доказать, что

3n² <= 4n² + 3n - 5

Это эквивалентно доказательству

4n² + 3n  - 5 - 3n² >= 0 (for n >= n0)
n² + 3n - 5 >= 0

Мы знаем, что эта функция является параболой, и мы знаем знакдоминирующего термина (n²) является положительным.Так что это должна быть парабола в форме долины.

Чтобы найти подходящее значение для n0, мы можем взглянуть на корни параболы.Они -1,844 и 0,844 (округлены).Таким образом, предполагая, что n0 = 2 будет достаточно.Вкратце:

n0 >= 2  
c1 = 3  
c2 = 5  

Если вы примените те же рассуждения к другой половине доказательства, вы получите еще одну оценку для n0.Затем все, что вам нужно сделать, это объединить обе границы.