[Solved]: Can subtracting o(1) from the parameter of a function change its Θ-class?

ignougroup
Problem Detail: 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?!

Asked By : wannabe programmer

Answered By : Yuval Filmus

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$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33074  Ask a Question  Download Related Notes/Documents