Big O Обозначения: Обоснование f (n) ∈ O (n ^ 4)?

Question

Это проблема с тетрадью Java.Я искал способ решить безуспешно.

Пусть f(n) = 100n^4+ 5000n+ 3. Is f(n)∈ O(n^4)? Если да, то обоснуйте свой ответ, указав соответствующие положительные константы c и n_0.

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

Заранее спасибо!

Answer 1

Вы можете доказать это таким образом,

100n ^ 4 + 5000n +3 <5000 (n ^ 4 + n + 1) для всех n> 1 ... (1)

5000 (n ^ 4 + n + 1) <5000 (n ^ 4 + n ^ 4 + n ^ 4) для всех n> 1 ... (2)

Что означает, что

100n ^ 4 + 5000n +3 <15000 (n ^ 4) для всех n> 1

Итак, доказано, что 100n ^ 4 + 5000n +3 - это O (n ^ 4)

Answer 2

Let f(n) = 100n^4+ 5000n+ 3

Для простоты, мы удалим всю константу

Let f(n) = n^4+ n

Мы будем использовать несколько арифметических для оценки:

Let f(n) = n^4+ n = n(n^3+1) 

Мы продолжим удалять константу

Let f(n) = n(n^3+1) = n*n^3 = n^4

Итак, финал

f(n)∈ O(n^4)

Пожалуйста, сообщите мне, если я что-то неправильно понимаю, я все еще изучаю Алгоритм.