HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?!

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$.

Context

StackExchange Computer Science Q#33074, answer score: 4

Revisions (0)

No revisions yet.