patternMinor
Can subtracting o(1) from the parameter of a function change its Θ-class?
Viewed 0 times
canthefunctionitssubtractingfromclasschangeparameter
Problem
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:
-
$g(n) = o(1)$
-
$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?!
-
$g(n) = o(1)$
-
$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?!
Solution
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$.
$$ 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$.
Context
StackExchange Computer Science Q#33074, answer score: 4
Revisions (0)
No revisions yet.