Big-O Notation and Asymptotic Bounds
You may have learned about big-O notation in your high school or college computer science course, but chances are you weren't told a good deal about asymptotic bounds in general. You see, big-O is just one kind of bound and there are several other kinds which may apply to a function. Also, I have noticed that a further understanding of asymptotic bounds is useful when thinking about limits involving infinity in the study of calculus. In this lesson, I'll discuss the four other types of asymptotic bounds (as well as review big-O).
First, it is important to clarify what big-O actually is. Technically speaking, it describes what is called an asymptotic upper bound. Rigorously, we can say that f(x) is an asymptotic upper bound of g(x) if and only if there exist constants k and xinitial, such that k times f(x) ≥ g(x) ≥ 0 for all values of x greater than xinitial. If f(x) is an asymptotic upper bound of g(x) this can be denoted by writing g(x) = O(f(x)). Basically, an asymptotic upper bound of a function is any function which eventually becomes greater than or equal to that function and stays greater than it forever, if it is multiplied by some arbitrary constant. It is important to note that even if f(x) is an upper bound of g(x), f(x) < g(x) can hold for all x. Because big-O denotes an upper bound, it should be used to describe the worst-case runtime of an algorithm.
Next up is big-Omega (denoted as Ω(something)). Ω denotes an asymptotic lower bound. Its rigorous definition is the same as big-O's, except that it f(x) is between (inclusive) zero and g(x) for all values of x greater than xinitial. Ω Notation should be used for specifying the minimum runtime of an algorithm.
Building on these two notations, we come to big-Theta notation (denoted as Θ(something). We can rigorously define Θ as denoting a function which is both an asymptotic upper and lower bounds. That is, g(x) = Θ(f(x)) if, and only if, g(x) = Ω(f(x)) and g(x) = O(f(x)). As you may be able to guess, big-Theta is an asymptotically tight bound. Some texts choose to define big-Theta separately and then prove the above definition as a theorem, but either way works. Also, some texts choose to use O to represent an asymptotically tight bound. My understanding is that the norm is to use Θ.
Since bounds denoted by both O and Ω may or may not be asymptotically tight and we have a means of specifying asymptotically tight bounds, it is also useful to specify a notation for bounds which are not asymptotically tight. Little-o notation and little omega notation (denoted as ω(something) provide this functionality. To define little-o rigorously, we change the rigorous definition of big-O to also specify that the inequality must hold for all k, rather than just some k, and change the inequality to further restrict f(x) to being greater than g(x), not greater than or equal to. For ω, the Ω definition is modified by making the first change above and changing less than or equal to less than in the same location as greater than was modified above.
If you want more information about asymptotic bounds, I suggest you check out chapter three of Introduction to Algorithms by Cormen et al. It is a wonderful text, and despite the fact that Amazon's reviews section has several complaints about the book being difficult to understand, I find that it is wonderfully concise, yet rigorous, and they really have no right to complain. The book contains many things I didn't have time to cover including identities.