If $f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ than can we say that $f(n)$ and $g(n)$ will never intersect?

  • 2
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Nov 12 '16 at 19:27
  • $\begingroup$ It's even possible for two functions to intersect infinitely often. (cc @YuvalFilmus) $\endgroup$ – Raphael Nov 12 '16 at 19:28

The asymptotic behavior of a function only depends on its value on "large" inputs. More formally, let $f$ be an arbitrary function, and let $f'$ be obtained by changing finitely many values of $f'$. Then for every function $g$, $f = O(g)$ iff $f' = O(g)$.

I believe that you can now answer your own question.


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.