1
$\begingroup$

I have encountered the following question in my homework assignment in Data Structures course:

"Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?"

I think no such function $f$ exists, but I do not know how to prove it (or give a counter-example if one exists).

Improve this question
$\endgroup$
1
  • $\begingroup$ For example, let $f(n)=n$ if $n$ is a square and $f(n)=1$ otherwise. For every $k\ge1$, $f(n-k) \ne \Theta(f(n))$ $\endgroup$ – John L. Aug 25 '20 at 18:52
1
$\begingroup$

An example is $f(n) = 2 ^ {2^n}$. Now, $f(n-1) = 2 ^ {2^{n-1}}$ and we have $\frac{f(n-1)}{f(n)} = \frac{1}{2^{2^n - 2^{n-1}}} = \frac{1}{2^{2^{n-1}}}$. Hence, $f(n-1) \not \in \Theta(f(n))$. In this example, $k = 1$.

Improve this answer
$\endgroup$
4
$\begingroup$

Counterexample: $f(n)=n!$ As $f(n)$ is $n$ times bigger than $f(n-1)$, it is clear that $f(n-1) \neq \Theta(f(n))$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.