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).

$\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$.

$\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))$.

$\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.