Big-Oh: Mathematical Definition
- Express the mathematical definition of Big-Oh.
Read it as
is a member of if and only if there exist positive constants and such that for all .
Here is a pictorial illustration of the above definition:

If you want to show that , you need to choose the constants and so that above definition holds whenever .
Exercise The running time of an algorithm is . Show that this algorithm has quadratic runtime, i.e., show .
Solution
We can choose and for the definition of Big-Oh to hold.
There is not a magic formula to find the constants. However, you can usually guess the values or deduct them by simple algebraic modification of .
Please note the choice of and are not unique. Moreover, these constants are not necessarily integers. According to the definition, these constants are non-zero and positive real values. Of course, if represents the program input size, then it is imperative to be an integer.
Please also note I have deliberately asked you to "show" and not "to prove." However, a proof generally would require finding a pair of and for the definition to hold. Of course, you should present your argument more formally. For example, the following would make reasonable proof. Notice I deliberately chose a different pair of and from those selected above.
Proof: Let's set . Now suppose that . Then by algebraic simplification, we get , and thus . So by the counterpositive, for all . So if we set , we have proved that for for all . Thus we have proved that . Q.E.D.
Resources
- Khan academy's article on Big O notation.
- Wikipedia's entry on Big O notation.
- This article is well written: Big-O Notation — A Primer.