Introduction
When considering the design of algorithms and the closely related subject of data structures, one needs to think about performance. While ease of use, maintainability, and such are also important, performance tends to be king. Performance includes both time—the amount of operations done—and memory usage—how much memory must be used by the process.
But how do you evaluate the performance of an algorithm? Just time it? Measure the memory usage? Count the lines of code? Well, practical implementations of any algorithm will vary across multiple systems—as will running time. So, then, what?
The answer is by analyzing its order of complexity. An order of complexity relates the size of the input to the running time or memory usage. But I just said we can't judge based on running time! This is because we consider the order of complexity—as in, does the time increase linearly with larger input, or quadratically? An algorithm that increases linearly might do so with a very large (constant) slope, but we don't care - the point is that it is linear. Hence, the actual running time of any particular implementation is abstracted away; only the fundamental relationship between input and performance is cataloged.
Notation
There are three order notations used to classify algorithms; big-O, big-theta, and big-omega. Big-O is what you will be typically concerned with, as it catalogs the worst-case complexity. Many algorithms are able to run in a smaller order with some inputs, but must fall back to a larger complexity in many cases. Hence, you optimize for the worst case. Big-theta describes the average complexity, and big-omega describes the best case. Most of the algorithms we will cover will have the same average and worst-case complexity.
The actual notation looks like this:
O(n) | Θ(n) | Ω(n)
Where 'n' denotes the size of the input. This size can mean different things for different algorithms, but it should be pretty clear how it applies. For example, for sorting algorithms, which we will look at shortly, the size of the input is the amount of numbers to sort. In this example, the amount of time needed to run the algorithm increases linearly with the input size. This means that an input of 100 elements should take 10 times the time as an input of 10 elements.
Big-O notation is asymptotic (remember your algebra II?), meaning that it describes the behavior of the function as 'n' approaches infinity. Hence, big-O drops all lower-order terms and constants.
For example, an equation with both an 'n' squared and an 'n' term, such as
10*n^2 - 12*n + 42
would be reduced to
O(n^2)
as the lower order linear term (linear < quadratic) and constants are removed. In this example, the time scales quadratically with the input size. Hence, an input of 100 elements should take 100 times the time as an input of 10 elements.
Classes of Complexity
Here several common orders of complexity by growth rate:
log(n) n n*log(n) n^2 n^3 2^n n!
Examples
The next section, sorting algorithms, will explain how to apply this concept to real algorithms.