Una funzione $ f $ esiste tale che: $ f (n-k) \ ne \ theta (f (n)) $ per alcuni $ k \ geq1 $?

Question

Ho riscontrato la seguente domanda nel mio compito a casa nei corsi di strutture dati:

"fa una funzione $ f $ esiste tale che: $ f (nk) \ ne \ theta (f (n)) $ per qualche costante $ k \ geq1 $ ? "

Penso che nessuna funzione tale $ f $ esiste, ma non so come dimostrarlo (o dare un contro-esempio se uno esiste).

.

Answer 1

Un esempio è $ f (n)= 2 ^ {2 ^ n} $ .Ora, $ f (n-1)= 2 ^ {2 ^ {n-1}} $ e abbiamo $\ frac {f (n-1)} {f (n)}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {n-1}}} $ .Quindi, $ f (n-1) \ non \ in \ theta (f (n)) $ .In questo esempio, $ k= 1 $ .

Answer 2

controexample: $ f (n)= n! $ come $ f (n) $ è $ N $ Times più grande di $ f (n-1) $ , è chiaro che $ f (n-1) \ neq \ theta (f (n)) $ .