Big Theta Notation
When most people talk about bigoh notation, they are more accurately referring to what Donald Knuth describes as bigtheta notation. Technically, bigoh notation refers to an upper bound. For example, seven is an upper bound of six; so are 9, 12, and 65. Subsequently, when most people discuss function growth they talk about the least upper bound, or a function that models both the upper and lower bounds. Professor Knuth, the father of the field of algorithmic analysis, describes this as bigtheta notation and gives the following definition:
If f(x) is bigtheta of g(x), then g(x) is both an upper bound and a lower bound for f(x).
Then, you can say that f(x) is of order g(x). The order, or bigtheta, of an algorithm is one of the most important mathematical tools for understanding algorithms in the kernel.
Consequently, when people refer to bigo notation they are more often talking about the least such bigo, the bigtheta. You really do not have to worry about this, unless you want to make Professor Knuth really happy.
