¿Existe una función $ f $ de manera que: $ F (n-k) \ ne \ theta (f (n)) $ para algunos $ k \ geq1 $ constante?

Question

He encontrado la siguiente pregunta en mi tarea asignada en estructuras de datos Curso:

"hace una función $ f $ existe de tal manera que: $ f (nk) \ ne \ theTa (F (n)) $ para algunos constantes $ k \ geq1 $ ? "

Creo que no existe tal función $ f $ , pero no sé cómo demostrarlo (o dar un ejemplo de contador si existe).

Answer 1

Un ejemplo es $ f (n)= 2 ^ {2 ^ n} $ .Ahora, $ f (n-1)= 2 ^ {2 ^ {n-1}} $ y tenemos $\ frac {f (n-1)} {f (n)}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {n-1}}} $ .Por lo tanto, $ F (N-1) \ NO \ IN \ THETA (F (N)) $ .En este ejemplo, $ k= 1 $ .

Answer 2

contraejemplo: $ f (n)= n! $ como $ f (n) $ es $ n $ veces más grande que $ f (n-1) $ , está claro que $ F (N-1) \ NEQ \ THETA (F (N)) $ .