Какая пара функций удовлетворяет f (N) ~ g (N)?

Question

Какая пара функций удовлетворяет f (N) ~ g (N)?

1. (N + 1) (N + N) и 2 н
2. (N + 1) (N + N) и N^3
3. журнал N + войти 3N и 3 § п
4. 2^N и 2^N + N^2

Я не уверен, что ответ равен 3 или 4. Две функции здесь одинаково почти одинаковы, и вывод их также почти одинаковый, когда я помещаю некоторые значения в них, но как я узнаю, какой из них правильный?

Answer 1

f ~ g означает f (x)/g (x) -> 1 при x-> бесконечности (или, что то же самое, g (x)/f (x) -> 1 при x-> бесконечности).

Ответ: (4): (2^N + N^2)/(2^N) = 1 + N^2/2^N. Последний член (N^2/2^N) стремится к 0 (быстро!) Как N-> бесконечность.

(3) неверен, поскольку logN + log3N = 2logN + log3, поэтому (logN + log3N)/3logN -> 2/3 как N-> бесконечность.