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

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