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

Question

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

Например .. проблема, с которой мне нужна помощь, заключается в том, чтобы показать, что 5n² - 6n = Θ(n²).

Я получил часть Big-Oh проблемы (я большой-Oh и Ω отдельно правильно?), Чтобы:

6k² >= 5n² - 6n 

и большой омега части к:

5n² - 6n >= n² 

.... но куда я иду отсюда?! Я помню из индукции что-то вроде ... Я предполагаю, что это правда, и теперь подключайте (n+1) для каждого n и ... сделайте .. что-то? Я потерял себя в этот момент.

Answer 1

Чтобы показать, что 5n^2-6n является O (n^2), вы должны доказать утверждение, что 5n^2-6n < = cn^2 для всех чисел n> = n0, для некоторого числа n0 и константа c.

Доказательство по индукции включает в себя подтверждение претензии для базового футляра и подтверждение этапа индукции. В нашем примере мы видим, что основной случай, когда n = 1, очевидно, справедлив для некоторой константы c.

Для шага индукции предположим, что утверждение верно для некоторого числа k и использует его, чтобы показать, что утверждение верно для k + 1. Таким образом, мы предполагаем, 5к^2-6k < = ск^2 и шоу:

5(k+1)^2 - 6(k+1) = 5k^2 +10k + 5 -6k - 6 
        = 5k^2-6k + 10k -1   
        <= ck^2 + 10k - 1 
        <= ck^2 + c*2k + c  (for any constant c >= 5) 
        = c(k+1)^2 

Это доказывает утверждение для к + 1 и завершает доказательство.

Вы можете доказать, что большая претензия Omega аналогична.