Big O Example – Graph

Hi everyone. I see that many of you have submitted your Test #1 review exercises and are making corrections already…that’s great! I’ll take a look at them tomorrow after class. Don’t forget to tag your post with the category “Test #1 Review” on the right side of the screen.

In the meantime…some of you are still having trouble understanding Big O notation. I can’t stress enough how important the definition on page 205 is. It’ll be impossible to understand what calculations to perform without at least an understanding of the definition. We discussed the way to think about it graphically in class and during office hours, and I just wanted to share an example here.

You can use this graph to see why is . Remember that the definition says that there must exist a pair of positive constants so that whenever , the inequality is satisfied. On the graph in the link, you get to play with the slider tools on the left side of the screen to change the values of and . Your goal is to find a pair so that whenever a point is in the green region, the red graph is below the blue graph. (In this case, since all -values are non-negative, you can add the absolute value bars without changing anything.)

You’ll see that there will be very many possible choices for . If you were proving that  is by hand, you might find one particular choice is easiest to work with. Because the definition involves an existence statement, you just need to find one pair that works.

Hope this helps!