Est-ce qu'une fonction $ f $ f $ existe de telle sorte que: $ f (n-k) \ ne \ theta (f (n)) $ pour une k \ geq1 $ constante?

Question

J'ai rencontré la question suivante dans mon attribution des devoirs dans les structures de données Course:

"fait une fonction $ f $ existe tel que: $ f (nk) \ ne \ theta (f (n)) $ pour une constante $ k \ geq1 $ ? "

Je pense qu'aucune fonction de ce type $ f $ existe, mais je ne sais pas comment le prouver (ou donner un contre-exemple si on existe).

Answer 1

Un exemple est $ f (n)= 2 ^ {2 ^ n} $ .Maintenant, $ f (n-1)= 2 ^ {2 ^ {n-1}} $ et nous avons $\ frac {f (n-1)} {f (n)}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2 2^ {n-1}}} $ .Par conséquent, $ F (N-1) \ PAS \ IN \ THETA (F (N)) $ .Dans cet exemple, K= 1 $ .

Answer 2

contre-exemple: $ f (n)= n! $ comme $ f (n) $ est $ N $ fois plus grand que $ f (n-1) $ , il est clair que $ F (n-1) \ neq \ theta (f (n)) $ .