Graphing Tool Documentation
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
+ 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
over f(n) at around 50. There are n0 = 50 and
c = 13 such that f(n) <=
Thus, f(n) = O(g(n)).
You may also want to experiment the following cases:
1000 = O(log n) [Enter: log n]
log n = O(n^0.1)
5^n = O(n!) [Enter: n!]
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
4. Tool Reference
Constant: e.g., 1 (integers) and 2.34 (floating-point
numbers, requires both sides of the decimal point)
Factorial: only the fixed form of n!
Power: Exp^Exp where Exp is a valid
expression. Exp other than a constant or n
Logarithm: log [Base] NonConstantExp where
is an option constant and NonConstantExp is a valid non-constant
expression. NonConstantExp other than n requires
parentheses. If Base is omitted, the default base of 2 is
Complex expressions can be formed by using the operators *,
and parentheses ( and ).
and / takes precedence over + and -.
The operators are left associative.
Spaces are ignored internally. Thus, you can write logn
for log n, etc.
sqrt(n) must be entered as n^0.5.
To set a specific c value, enter the number and press Draw Graph.
The scroll bars may behave strangely.