Graphing Tool Documentation

1. Introduction

This Java applet is prepared so that you can explore the the idea behind the Big-O notation in a graphic and dynamic way.

2. Tutorial:  Visual Experience of Big-O Notation

Let us first observe the case of n^10 = O(2^n).  Let f(n) = n^10 and g(n) = 2^n.  Enter n^10 and 2^n in the first and second text fields, respectively.  You now must be able to see a series of red dots corresponding to 2^n (the values for n^10 are out of range).  If you don't see it, check the expressions in the text fields.  Invalid expressions would show "Expression syntax error" or "Parenthesis mismatch".  Also check the initial setting of n and y ranges and the c value are 10^1, 10^3, and 1.0, respectively.  By clicking the top triangle of the vertical scroll bar, change the y scale to 10^10.  You now must be able to see both red and blue dots, the latter corresponding to n^10.  Thus, up to n = 10, we can tell that n^10 grows much faster than 2^n.  Extend the range of n to 10^2.  Then, increase the range of y gradually to 10^19.  You must now see that 2^n outpaces n^10 at around 60 (59, to be precise).  Provided that this trend continues beyond this point (a formal proof is needed to make sure this point), we can say that after n0 = 59, 2^n is greater than n^10.  Thus, n^10 = O(2^n).

Next, observe the case of f(n) = 10*n^2 + 100*n + 1000 = O(g(n)) = O(n^2).  Enter 10*n^2 + 100*n + 1000 and n^2 in the respective text fields (the multiplication symbol * is necessary).  Set the n and y ranges to 10^2 and 10^5, respectively.  Naturally, f(n) grows much faster than g(n).  Then, change the c value by sliding the scroll bar to its right.  If you set the c value at around 13, you should be able to see that g(n) takes over f(n) at around 50.  There are n0 = 50 and c = 13 such that f(n) <= c*g(n).  Thus, f(n) = O(g(n)).

You may also want to experiment the following cases:

3.  Limitations of the Visual Inspection

Suppose that we attempt to show that n*log n is O(n), which is incorrect.  Set the n range to 10^14 (the max).  Adjust the y range to appropriate for viewing, say, 10^16.  If you adjust the c value above around 50, it appears as if n outpaces n*log n for the entire n range.  But this is not right.  We simply cannot see that n*log n outgrows n at some point beyond the max n range available for this tool.  So, although it is often helpful to show the relation between two functions, it is limited to the max ranges of n and y of this tool.  The only way to show a certain asymptotic relation in general is to prove formally.

4. Tool Reference

Basic functions Complex expression Notes <End>