Мне нужна помощь в доказательстве того, что если f (n) = O (g (n)), то log f (n) = O (log g (n)) равно FALSE

Question

Пусть функции f и g такие, что f (n) есть O (g (n)) и следующие операторы:

I. log f (n) равно O (log g (n))
II. 2 ^{f (n)} - это O (2 ^{g (n)} )
III. f (n) ² - это O (g (n) ² )

Какое из следующих утверждений является / является ложным?

A. I и II
B. I и III
C. II и III
D. Все I, II, III

Объяснение:

Только утверждение (III) f (n) ² - это O (g (n) ) ² ) является верным.

Опция (A) верна.

Решение говорит, что только утверждение 3 является правильным, остальные 2 неверны.

Я понимаю, что II неверен, потому что f (n) может быть 2n, а g (n) может быть n; тогда f (n)! = O (g (n)), но как утверждение I ложно?

Answer 1

Утверждение I неверно, и вот почему. Пусть f (n) = 2 и g (n) = 1. Тогда f (n) = O (g (n)). Однако log (f (n)) = 1 и log (g (n)) = 0. Нет ни n0, ни c таких, что 1 <= c * 0. </p>

РЕДАКТИРОВАТЬ: предположительно, оператор II не отформатирован должным образом и должен читать 2 ^ f (n) = O (2 ^ g (n)), что неверно, если f (n) = 2n и g (n) = n, например