I would like to know if it is possible that two functions $f(n), g(n)$ can exist such that both of the following conditions are met:

  1. $g(n) = o(1)$

  2. $f(n-g(n)) \neq \Theta (f(n))$

I though I found $1/n$ and $1/n^2$ but I think I got it all wrong.

Is it even possible?!


Let $g(n) = 1/n$ and define $$ f(n) = \begin{cases} n & \text{if $n$ is an integer}, \\ \log \lceil n \rceil & \text{otherwise}. \end{cases} $$ For an integer $n>1$, $f(n) = n$ while $f(n-g(n)) = \log n$.

| cite | improve this answer | |
  • $\begingroup$ And again, the question arises: what about continuous functions? (As far as I can tell, the definition of continuity mandates that $f(n - g(n)) = f(n)$ holds in the limit for all $g$ that tend to zero. $\endgroup$ – Raphael Nov 13 '14 at 17:19
  • 1
    $\begingroup$ @Raphael Since it is enough to demand that $f(n) = n$ and $f(n-1/n) = \log n$ for all integers $n>1$, it is probably possible to construct a $C^\infty$ function $f$ going through all these points. $\endgroup$ – Yuval Filmus Nov 13 '14 at 18:41
  • $\begingroup$ I imagine the OP was assuming f was monotonically increasing. $\endgroup$ – Lembik Nov 25 '14 at 21:57
  • $\begingroup$ @lembik I don't, since they considered the example $f(n)=1/n$. $\endgroup$ – Yuval Filmus Nov 25 '14 at 22:10
  • 1
    $\begingroup$ It looks to me that the OP meant $g(n) = o(1)$ and $f(n)$ monotonically increasing but I could be wrong. $\endgroup$ – Lembik Nov 26 '14 at 6:19

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.