Uma função $ F $ existe tal que: $ f (n-k) \ ne \ theta (f (n)) $ para alguma constante $ k \ geq1 $?

Question

Eu encontrei a seguinte pergunta em minha tarefa de casa no curso de estruturas de dados:

"A função $ F $ existe tal que: $ f (nk) \ ne \ theta (f (f (fn)) $ para alguma constante $ k \ geq1 $ ? "

Eu acho que nenhuma função $ F $ existe, mas eu não sei como provar (ou dar um contra-exemplo se existir).

.

Answer 1

Um exemplo é $ f (n)= 2 ^ {2 ^ n} $ .Agora, $ f (n-1)= 2 ^ {2 ^ {n-1}} $ e temos $\ frac {f (n-1)}}} {f (n)}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {N-1}}} $ .Assim, $ f (n-1) \ não \ in \ theta (f (n)) $ .Neste exemplo, $ k= 1 $ .

Answer 2

contraexemplo: $ f (n)= n! $ como $ f (n) $ é $ n $ vezes maior que $ f (n-1) $ , é claro que $ f (n-1) \ neq \ theta (f (n)) $ .