Два вопроса относительно обозначений Big-O, Theta и Omega

Question

Докажите или опровергните следующие утверждения:

1. Существующая функция f(n), поэтому f(n-k) не равно Big-theta (f(n)). когда k>=1 и положительная константа.

Есть ли функция, для которой это утверждение верно? Я думал о f(n)=n!, но я не уверен, что это правильный ответ. Кроме того, если f(n)=n! правильно, как это утверждение может быть доказано?

2. Существуют функции, поэтому (f(n))^2=Big-O(f(n)) и f(n)=Big-omega (log(log(n))).

Я думаю, что нет функции, которая делает утверждение правдивым. Если это правильно - как это можно доказать?

Answer 1

1. Исправьте для f (n) = n !.Достаточно показать, что для любого фиксированного k> = 1 (n - k)!не является Omega (n!), как и для любой константы c> 0, оно выполняется для всех достаточно больших n, что c * n!> (n - k)!.

2. Не существует f (n) такого, что оба f (n) ^ 2 = O (f (n)) и f (n) =Омега (журнал журнала N).Последнее подразумевает, что для некоторой константы c> 0 и всех достаточно больших n f (n)> c log log n и, в частности, f (n)> 1 для всех достаточно больших n.Если теперь предположить, что f (n) ^ 2 = O (f (n)), то существует постоянная r> 0, так что для всех достаточно больших n f (n) ^ 2 e ^ (e ^ (r / c)) (где e - основа log).