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 &gt; 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?
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.