если f (n) = 2n ^ 2 и g (n) = 1,01 ^ n.Является ли f (n) = O (g (n))?Является ли f (n) = Ω (g (n))?

Question

Пусть f (n) = 2n ^ 2 и g (n) = 1,01 ^ n.Является ли f (n) = O (g (n))?Является ли f (n) = Ω (g (n))?Обоснуйте свои ответы доказательством.

Answer 1

Подумайте, как выглядят графики этих функций для очень больших n.Какой из них растет быстрее (т.е. обгоняет другого в долгосрочной перспективе)?Временные сложности обозначают асимптотическое время выполнения алгоритма.