Существует ли функция $ F $ такова, что: $ f (n-k) \ ne \ theta (f (n)) $ для некоторой постоянной $ k \ geq1 $?

Question

Я столкнулся с следующим вопросом в моем домашнем задании в курсе структур данных:

"делает функцию $ f $ такой, что: $ f (nk) \ ne \ ne \ iteta (f (f (n)) $ для некоторой постоянной $ k \ geq1 $ ? "

Я думаю, что нет такого функции $ F $ существует, но я не знаю, как это доказать (или дать контр-пример, если кто-то существует).

.

Answer 1

Пример - $ f (n)= 2 ^ {2 ^ n} $ .Теперь $ f (n-1)= 2 ^ {2 ^ {n-1}} $ , и у нас есть $\ frac {f (n-1)} {f (n)}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {N-1}}} $ .Следовательно, $ f (n - 1) \ not \ in \ theta (f (n)) $ .В этом примере $ k= 1 $ .

Answer 2

Counterxample: $ f (n)= n! $ как $ f (n) $ $ n $ раз больше, чем $ f (n - 1) $ , понятно, что $ f (n - 1) \ neq \ theta (f (n)) $ .