Большой О (Доказательство Индукции) - PullRequest
0 голосов
/ 30 ноября 2010

Если f (n) = 15n ^ 3 + 7n ^ 2 + 34 & g (n) = n ^ 4 + 3n ^ 2 + 17. Как мне доказать, что f принадлежит O (g)?

1 Ответ

0 голосов
/ 30 ноября 2010

Хорошо, определение обозначения Big-O следующее:

f в O (g) <=> существует c, n0 такое, что для всех n> = n0, | f (n) | <= c | g (n) | </p>

Таким образом, в этом случае проще всего продемонстрировать, что f находится в O (g), найдя подходящие c и n0, удовлетворяющие всем n> = n0, | 15n ^ 3 + 7n ^ 2 + 34 | <= c | n ^ 4 + 3n ^ 2 + 17 |. Я думаю. </p>

...