Runtime complexity is a measure of the efficiency of an algorithm as it scales to larger and larger data sets. Complexity is denoted with an upper-case O followed by a complexity measure in parentheses, called big O notation. The expression inside the brackets describes the algorithm’s duration, given input data of size n.

When an algorithm takes twice as long with twice the number of input values or three times long with three times as many input values, it is said to have linear complexity, denoted by $O(n)$. However if an algorithm takes four times as long with twice the values and nine times long with triple the values, it has quadratic complexity, which would be written as $O(n^2)$. The faster the n-expression grows for bigger values of n, the worse an algorithm scales.

An Example

Consider an algorithm meant to determine whether a given value is already part of a given collection. If the values in the collection are stored without rhyme or reason, every value must be compared against the test value, or at least until a match is found. Of course the function may get lucky and find a match right away, but it is equally likely to be found at the last value. Therefore on average half the collection will need to be checked when there is a match and the entire collection will need to be checked when there are no matches. Either way if the collection is twice as big it will involve twice as many comparisons, thus such an algorithm has linear complexity.

If the values in the collection are stored in a sorted fashion, a faster approach becomes possible. The algorithm can now disregard large swaths of the collection during every iteration. Imagine for example a list of one million numbers sorted from small to large and the algorithm is asked whether 584 is present in this collection. By checking 584 against the middle value, all 500,000 values to the left or the right of the middle can instantly be ignored as they are all guaranteed to be either smaller than or larger than 584. This new search method improves the complexity to $O(\log (n))$. An algorithm with logarithmic complexity scales much better to larger datasets. For example it might return an answer in 10ms for 100 values, 20ms for 1000 values, and 30ms for 10,000 values.

Sticking with our current example, hash tables are data structures specifically optimised for clash detection and operate with constant time complexity, or $O(1)$. It matters not how big the dataset is, a hash table will always find matches in the same amount of time.

Multiple Input Sets

Oftentimes algorithms operate on more than one dataset, in which case the big-O notation may include more letters than just n. For example an algorithm operating on two collections might be classified as $O((n+m{)}^2)$ or $O(n\cdot m)$, where n is the size of the first collection, and m the size of the second.

Simplifying n-expressions

Given that the complexity measure is most relevant for large data sets, less significant components in the complexity expression will often be omitted from the notation altogether. For example $O(n^2+2n+1)$ will be simplified to just $O(n^2)$ as that is the dominant factor; as n gets bigger and bigger the relative contribution of the less significant terms 2n and 1 approaches zero percent.

Note that runtime complexity is not exactly the same thing as speed. Two algorithms with the same complexity may well take wildly different times to run to completion given the same input. Sharing the same complexity merely means they slow down in the same way given an increase in the input size. It is even possible for algorithms with an objectively worse complexity like $O(n)$ to outperform "better" algorithms like $O(\log (n))$, provided the input size is sufficiently small. Since the complexity measure describes the performance in the limit case, it is less reliable for small values of n. However such considerations are rarely a factor when choosing an algorithm, given that pretty much all algorithms are fast when confronted with a small data set, rendering a preference of one over another moot.

The usefulness of a complexity measure often depends on context. Furthermore many algorithms may have differing runtime complexities for best case, worst case and expected case scenarios. The likelihood of best case or worst case scenarios in a given production environment may influence the choice of one algorithm over another.

O-Notation Algebra

There are two possible approaches for determining the runtime complexity of an algorithm. The easiest and most reliable way is to simply measure the performance and fit an n-expression to the results. This however means designing and executing an experiment, so it is a time consuming approach. The answer is also unlikely to be neat due to the inherent noisiness of algorithms running on multi-tasking systems. Perhaps the best fit is found to be $O(n^{1.73})$, which is an unlikely complexity as exponents in n-expressions tend to be integers or nice fractions. It now becomes a matter of debate whether the exponent is really supposed to be 2 or 1.5 or something else.

It is however often possible to analytically determine the complexity of an algorithm. Many common algorithms have proven complexities, usually for the worst case performance, but sometimes even for expected or special cases.

The exact algebra involved is beyond the scope of this text, but there are some handy rules which allow for a decent guess. A loop running across a fixed portion of the collection has linear complexity $O(n)$. The complexity of any instructions inside a loop will be multiplied by the loop complexity. For example if the loop body executes a binary search with complexity $O(\log n)$, the loop as a whole will have complexity $O(n)\cdot O(\log (n))=O(n\cdot \log (n))$.

Similarly, a loop nested inside another loop, both iterating over a portion of the n-collection, will yield complexity $O(n\cdot n)$, or $O(n^2)$ for short. An algorithm with four nested loops with the innermost one containing a logarithmic instruction, yields a total complexity of $O(n^4\cdot \log (n))$, which is objectively atrocious. Assuming an algorithm with this complexity finishes in one millisecond given an input of ten values, it will take twenty seconds to solve a hundred values and three-and-a-half days to solve a thousand.

When instructions are executed in sequence rather than nested, their complexities are added together. This operation however is almost always meaningless as the worst of the two steps will dominate the limit behaviour meaning the lesser complexity can be omitted. Case in point, an algorithm executing three consecutive steps, with respective complexities of $O(n)$, $O(\log (n))$, and $O(n!)$, would theoretically be $O(n+\log (n)+n!)$, which reduces to just the most significant factor $O(n!)$.

It is very difficult to analytically determine the runtime complexity of recursive algorithms. Sometimes it can be done, but it almost always requires intricate mathematical proofs. Since developing recursive algorithms using Grasshopper is difficult any way, this text does not concern itself with any further details.

Conclusion

Runtime complexity and Big-O notation are the subject matter and representation of choice for algorithm analysis. It is one of the more mathematically dense areas of computer science and unless one develops one's own performance critical algorithms it is unlikely to be of interest.

However even users and intermediate stage programmers will oftentimes encounter algorithms which do not scale well to larger problems and as such may become prohibitively slow. Attempts to resolve these performance issues will require at least a beginner level understanding of runtime complexity.