# Are there functions in the same Θ-class that are not linear transformations of each other?

looking for some help, or at least if I'm going the right direction...

Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c_1$ and $c_2$ exist for which $f(x) = c_1 \cdot g(x) + c_2$?

I want to say that there is not, because the definition of big O states that if $f(x)$ is $O(g(x))$ then $|f(x)| \leq c_1 \cdot |g(x)|$ for all values $x > k$

and if $f(x) = c_1 \cdot g(x) + c_2$ then $g(x) = \frac{f(x) - c_2}{c_1}$

and thus $0 \leq f(x) \leq c_1 \cdot g(x)$

$0 \leq c_1 \cdot g(x) + c_2 \leq c_1 \frac{f(x) - c_2}{c_1}$

$0 \leq c_1 \cdot g(x) + c_2 \leq f(x) - c_2$

$0 \leq c_1 \cdot g(x) \leq f(x)$

Which contradicts the initial definition of $f(x)$ being $O(g(x))$.

Am I on the right path, here?

• Consider the functions $f(n) = 1$ and $g(n) = sin(n\pi/2) + 2$. I think you'll find that both are $O$ of each other... but you won't find constants that make one a linear function of the other (well, unless you allow multiplying by 0, in which case just choose another sine function for $f$ but with a different phase... or take $f$ for $g$ and vice versa). – Patrick87 Oct 2 '14 at 5:02
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Oct 2 '14 at 5:17
• Hint: You can find two such functions $f,g$ by taking two "generic" quadratic polynomials. – Yuval Filmus Oct 2 '14 at 5:51

Your proof must be wrong since the result is incorrect. For example, if $f=x^2$ and $g=x^2+x$ then $f = \Theta(g)$ but $f$ is not an affine shift of $g$. To see where the proof goes wrong, I suggest substituting these $f$ and $g$ in the proof and seeing which step fails. This is how one debugs their proof.
Take $f(n) = n + log(n)$ and $g(n) = n$.
1. You don't prove that $0 \leq f(x) \leq c_1 \cdot g(x)$.
2. You don't explain why $c_1 \cdot g(x) \leq f(x)$ contradicts $f(x)$ being $O(g(x))$.