Big Oh (Induction Proof)

Question

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

Answer 1

Хорошо определение Большой-O записи выглядит следующим образом:

F в O (г) < => существуют с, n0 такое, что для всех п> = n0, | F (п) | < = c | g (n) |

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