1
$\begingroup$

Say we have: $$f(n) \in O(g(n))$$ By definition we need to show that: $$0 \le f(n) \le c\cdot g(n) $$ for some $c>0$ and for all $n>n_0$.

This is usually not difficult when rational and polynomial functions are involved, but if functions have logarithms and square roots, I get confused and not sure how to proceed. I know there has to be a calculus proof, but I'm unaware of it.

Would it be enough to show that: $$c\cdot g(n) - f(n) \ge 0 $$

And to do that we need to find the minimum point by deriving it (which we can use as n0), and showing that the slope is always positive?

  • 1
    Could you add a concrete example that you have difficulty with? That would make it much easier to give an instructive answer.2012-05-12
  • 0
    A function may have a positive slope on $I=[x_0,+\infty)$ without being positive at any point in $I$.2012-05-13

1 Answers 1