As a software developer, no matter what you create, or where you are in the chain of an application, front end, back end, mobile, it doesn’t matter, there are limited resources to be managed.

Those resources may be tangible, such as CPU, RAM, disk, network, or intangible, like time, or frustration of your users.

The cost, or usage, of the resources isn’t fixed, there are factors that change how much of each is going to be used by an application or system, at a given point in time. That is the amount of resource used by your application changes with the amount of usage it gets, and the amount of data it needs to process.

To make this concept slightly more concrete, typists will be familiar with the idea that how fast they type is measured in WPM (words per minute). That is, the determination of how long a given typist is going to take to type a document of a given length is as simple as the number of words in the document divided by the words per minute pace that that typist maintains. A car driver’s journey time will be determined by the velocity, measured in miles or kilometers per hour, divided by the distance to travel. Caterers will know that they need to determine how much food to cook by knowing how filling the food is and multiplying that by the number of people they are expected to feed.

A software developer has a metric available to them, the big O notation, that has been shamelessly stolen from other disciplines (Mathematics!). The big O notation describes how much work an algorithm will do to handle different workloads.

Again, a more concrete example may make it clearer.

If i write some code, say a search. My algorithm will search through a big bucket of data looking for the piece I want. Each time that my algorithm finds a piece of data, it needs to check if that piece of data is the piece I have asked for. The comparison cost in time might be measured as a few nanoseconds, but we know that the total cost of each search made by my algorithm is actually based on how much data there is to search through.

The best case is for the algorithm is, by a complete stroke of luck, randomly pick a piece of data and it’s the piece I am looking for. Life, however, hasn’t bestowed upon me, or my algorithm, that sort of luck. The worst case, assuming that my algorithm only looks at each item once, is that the last piece of data in the bucket is what I am looking for. And the average case would expected to be somewhere in the middle.

This is where big O notation comes in, it describes the amount of work in relation to the amount of data that is being dealt with.

Big O notation shows the time (or space) complexity of a given algorithm, the following are some of the more common time or space complexities.

Constant time, or space. O(1)

If the amount of work to be done is the same, regardless of the amount of data, that’s a constant An example of constant time might be “finding the middle between two points” - no matter how far apart those points are, the middle is always going to be calculated taking the difference between the two points and dividing by two.

Note, and this is important, just because various algorithms might be constant time, it does not mean they’re all taking the same amount of actual time as one another. For example the hashing algorithm for a hashmap is considered constant, because no matter how many keys it is given, calculating the hash is always going to take the same amount of time, but, the hashing algorithm chosen will affect how long that calculation takes, and this will be much longer than the amount of time to calculate the midpoint of an array.

That is, finding the midpoint of an array might take a few nanoseconds, the task requires a lookup of the start and end of the array, a subtraction, and a division. Hashing will take many orders of magnitude more effort, to produce a key for a given input, and then adjust if there’s a collision (that key’s location is already taken). But the hashing algorithm will have the same number of steps each time.

Logarithmic. O(log n)

The sad fact of life is that constant time is only applicable to a few algorithms, the rest will take more time, or space, as the amount of input to deal with grows. There are a couple of steps between constant and logarithmic time, but logarithmic is the most common next point to look at.

In order to search a sorted array of items for a value, it’s best to halve the problem each time. That is, to find where X is in an array (or if it even exists!) first find the middle of the array (which is constant time remember!) compare, and if X is smaller look at the half below the midpoint and the bottom, or if it is greater look in the top half. Each time the check is done, the size of the array left to search is halved (the algorithm will note where the current top, and bottom are, then update one or the other with where the current middle is and then calculate the new middle between the new top/bottom).

Because the size of the search space halves each time, we can predict how many searches it will take (worst case) to find the value we want, it’s the log2 of the size of the array. There is a table at the bottom of this article that shows how the size of the data being dealt with by a given algorithm influences the amount of work to be done, as related to the Big O notation for that algorithm.

Linear. O(n)

Some algorithms are going to look at every item to find some information, these are called linear algorithms, because the time taken grows at a linear rate in relation to the number of items being dealt with.

An example might be searching an unsorted array for the min, or max, value it holds. every item has to be checked to see if it is the min, max, or mid, or to be ignored.

Linearithmic.O(n log n)

The fastest sorting algorithms have a time complexity of n multiplied by log2 n, this is because every item must be touched (n) and putting it into the correct place takes log2 n. If I took an unsorted bucket of data, and placed it into a binary tree, each item would need to be touched (n) ans each insertion would cost log n, giving O(n log n)

Quadratic. (O n²)

Slower, naive sorting algorithms are quadratic. Insertion, bubble, and selection sort fall into this category. These sorting algorithms will check each value against every other value, that means n*n (or n²) checks.

Cubic. (O n³)

An example of this is naive matrix multiplication, when two n by n matrices are multiplied together. Each item in each row in the first matrix is multiplied to each item in each column of the second matrix, and then values are all added together. This gives a O(mnp) complexity, where matrix 1 has dimensions of m by n, and the second matrix is n by p, when both matrices have dimensions n by n, then the calculation becomes O(nnn) or O(n³).

Exponential. O(2ⁿ)

Solving the Traveling salesman problem using dynamic programming, where previous results are cached, still takes 2 to the power of n computations.

Factorial. O(n!)

Things get worse when naive brute forcing is used to solve the Traveling Salesman problem. The lack of caching of previous results means that a lot of work is repeated.

It might be tempting to not want algorithms that fall into this category, or even categories that require more work, but they are actually very important. Cryptographic algorithms rely on the fact that finding the decrypted version of an encrypted value takes a lot of work, which translates to a lot of CPU time. For example, at current CPU speeds, exploring the hash space of (say) sha256, where you are looking for which input is used to generated which hash, will take many times the currently known age of the universe to compute.

The following table shows how the amount of work being done grows for each class of algorithmic time complexity.