Often, in computer science and related disciplines, it is useful to express the algorithmic complexity—or scalability—of algorithms as a meaningful value (as opposed to less descriptive terms, such as gross). Various methods exist for representing scalability. One common technique is to study the asymptotic behavior of the algorithm. This is the behavior of the algorithm as its inputs grow exceedingly large and approach infinity. Asymptotic behavior shows how well an algorithm scales as its input grows larger and larger. Studying an algorithm's scalability—how it performs as the size of its input increases—enables us to model the algorithm against a benchmark and better understand its behavior.
An algorithm is a series of instructions, possibly one or more inputs, and ultimately a result or output. For example, the steps carried out to count the number of people in a room are an algorithm, with the people being the input and the count being the output. In the Linux kernel, both page eviction and the process scheduler are examples of algorithms. Mathematically, an algorithm is like a function (or at least, you can model it as one). For example, if you call the people counting algorithm f and the number of people to count x, you can write:
| people counting function |
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.
When most people talk about big-oh notation, they are more accurately referring to what Donald Knuth describes as big-theta notation. Technically, big-oh 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[1]. Professor Knuth, the father of the field of algorithmic analysis, describes this as big-theta notation and gives the following definition:
If f(x) is big-theta 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 big-theta, of an algorithm is one of the most important mathematical tools for understanding algorithms in the kernel.
Consequently, when people refer to big-o notation they are more often talking about the least such big-o, the big-theta. You really do not have to worry about this, unless you want to make Professor Knuth really happy.
Consider the original example of having to count the number of people in a room. Pretend you can count one person per second. Then, if there are seven people in the room, it will take seven seconds to count them. More generally, given n people it will take n seconds to count everyone. Thus, you can say this algorithm is O(n). What if the task was to dance in front of everyone in the room? Because it would take the same amount of time to dance whether there were five or five thousand people in the room, this task is O(1). See Table C.1 for other common complexities.
Table C.1. Table of Common Time Complexity Values
O(g(x)) | Name |
|---|---|
1 | constant (perfect scalability) |
log n | logarithmic |
n | linear |
n2 | quadratic |
n3 | cubic |
2n | exponential (evil) |
| factorial (pure evil) |
What is the complexity of introducing everyone in the room to everyone else? What is a possible function that models this algorithm? If it took thirty seconds to introduce each person, how long would it take to introduce 10 people to each other? What about one hundred people to each other?
Obviously, it is wise to avoid complexities such as O(n!) or O(2n). Likewise, it is usually an improvement to replace an O(n) algorithm with a functionally equivalent O(1) algorithm. This is not always the case, however, and a blind assumption should not be made based solely on big-o notation. Recall that, given O(g(x)), there is a constant, c, multiplied by g(x). Therefore, it is possible that an O(1) algorithm takes three hours to complete. Sure, it is always three hours, regardless of how large the input, but that can still be a long time compared to an O(n) algorithm with few inputs. The typical input size should always be taken into account when comparing algorithms.
Favor less complex algorithms, but keep in mind the overhead of the algorithm in relation to the typical input size. Do not optimize blindly for some random case!
[1] If you're curious, the lower bound is modeled by big-omega notation. The definition is the same as big-o, except g(x) is always less than or equal to f(x), not greater than or equal to. Big-omega notation is less interesting than big-oh because finding functions smaller than your function is rarely interesting.