Big-O Notation

One useful asymptotic notation is the upper bound, which is a function whose value, after an initial point, is always greater than the value of the function that you are studying. It is said that the upper bound grows faster than the function in question. A special notation, big-o (pronounced big oh) notation, is used to describe this growth. It is written f(x) is O(g(x)) and is read as f is big-oh of g. The formal mathematical definition is

If f(x) is O(g(x)), then

c, x' such that f(x) c · g(x), x > x'

In English, the time to complete f(x) is always less than or equal to the time to complete g(x) multiplied by some arbitrary constant, so long as the input x is larger than some initial value x').

Essentially, you are looking for a function whose behavior is as bad as or worse than the algorithm. You can then look at the result of very large inputs to this function and obtain an understanding of the bound of your algorithm.