2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Patrick87 Oct 2 '14 at 5:02
  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Oct 2 '14 at 5:17
  • $\begingroup$ Hint: You can find two such functions $f,g$ by taking two "generic" quadratic polynomials. $\endgroup$ – Yuval Filmus Oct 2 '14 at 5:51
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Yes there are.

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

$\endgroup$
2
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.