1
$\begingroup$

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$ $$g \le c_1*f $$ $$h \le c_2*f $$

Now we have to prove, $$g = O(h)$$ $$g \le c_3*h$$ $$g \le c_3*c_2*f $$ $$ c1 \le c3*c2 $$ We can find $c_3$ such that last equation $ c1 \le c3*c2 $ will be true.

Is this correct or not? If not what will be correct proof for this?

$\endgroup$
1
$\begingroup$

$f(n)=n^2$, $g(n)=n$, $h(n)=1$.

$\endgroup$
  • $\begingroup$ Thank you for the test case. But is there any way we can mathematically prove $g = O(h)$ wrong. $\endgroup$ – user4828815 Sep 26 '18 at 20:13
  • $\begingroup$ This counterexample is a proof (though you could prove that $n\neq O(1)$ if you wanted -- that follows quickly from the definition of $O$). $\endgroup$ – David Richerby Sep 26 '18 at 20:15

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.