Growth and Big O

In this interactive demonstration, you can change the two functions and compare their graphs over a specified domain for $x$.

When it initializes, it shows a red and green graph. Which one grows faster? Really? Extend the domain of $x$ to $150$. Now what do you see?

We say $f = O(g)$ if, once you make the domain of $x$ big enough, and the constant out front of $g$ big enough, you discover that $f$ is eventually always below $g$. (Here I’m assuming $f$ and $g$ are positive functions.)

Here’s an example to try: set f = 500*log(x), and set g = x, and put xdomain=(1,100). It looks like $f$ is winning. Can you put a big enough coefficient on $g$ (e.g. g = 20*x etc.) and make the $x$ domain big enough (e.g. xdomain = (0,100) etc.), so that the red line is eventually staying below the green one? Can you do it just using the constant on $g$? Or just by extending the domain of $x$?

Other examples to try (determine if $f = O(g)$):

  • f = abs(sin(x)), g = abs(cos(x)). (I’ve put absolute values on these to keep them positive.)
  • f = abs(sin(x)), g = 0.5.