Is there a function $f(x)$ and a constant $k$ so that $f(x-k) \neq O(f(x))$?

Question

Is there a function $f(x)$ and a constant $k$ so that $f(x-k) \neq O(f(x))$?

If it exist, what is the function, and if it doesn't, what is the proof to that?

My intuition is that big O refers to the worst case, meaning worst x, so no constant should have a significant effect on the time complexity, but I'm not sure at all, and I'm struggling to write it formally.

Answer 1

As Christian Blatter commented, let $f(x)=e^{-x^2}$. Then $$ \begin{align} f(x-k) &=e^{-(x-k)^2}\\ &=e^{2kx-k^2}e^{-x^2}\\ &=e^{2kx-k^2}f(x) \end{align} $$ That is, for $k\gt0$, $\frac{f(x-k)}{f(x)}$ grows without bound as $x\to\infty$.

This means that $f(x-k)\not\in O(f(x))$.

Answer 2

I got an idea, would love some verification:

I will prove that no such function exist and that for any function $f(x-k)=O(f(x))$.

• To prove that, I will use proof by contradiction assuming that there is a function that for $f(x-k)\neq O(f(x))$ does hold.
• There for $\lim \frac{f(x-k)}{f(x)}=\infty$
• $\lim f(x)=\lim f(x-k)$
• If so, then $\lim \frac{f(x-k)}{f(x)}=\frac{\lim f(x-k)}{\lim f(x)}=1$, in contradiction to our assumption that $f(x-k)\neq O(f(x))\Leftrightarrow \lim \frac{f(x-k)}{f(x)}=\infty$.
• There for indeed $f(x-k)=O(f(x))\blacksquare$