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

Question

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?

Answer 1

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.

Answer 2

Yes there are.

Take $f(n) = n + log(n)$ and $g(n) = n$.

Answer 3

There are some wrong or unexplained points in your proof sketch. You need to justify these steps, if they are indeed correct.

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