Algorithmic time complexity

Learning out loud

Computer Science

Distinguishing algorithms from programs

Algorithms are general sets of instructions that take data in one state, follow a prescribed series of steps and return data in another state. Programs are a specific application of one or more algorithms to achieve an outcome in a specific context. When we think about the complexity of algorithms, the actual detail of the steps is mostly abstracted and it is irrelevant to what end the algorithm is being put. For instance you may create a program that returns addresses from a database using a postcode. It is irrelevant to the complexity of the algorithm whether or not you are looking up postcodes or some other form of alphanumeric string.

Algorithmic efficiency

Algorithms can be classified based on their efficiency. In the context of time complexity, efficiency is function of the algorithm's speed at runtime. However, we should not assume this means that "the fastest algorithms are best". We must be attentive to the particular use case. If we are landing the Curiosity Rover on Mars, we may choose an algorithm that is slower on average in return for a guarentee that it returns a value to some nth degree of accuracy. In other cases, for example a video game, we may choose an algorithm that keeps the average time down even if this occasionally leads to processes that need to be aborted because they take too long.

We need a generalised measure of efficiency to compare algorithms. We can't simply use the number of steps, since some steps will be quicker to complete than others in the course of the runtime and may take longer on different machines depending on the specific hardware. In fact the same algorithm will run at marginally different speeds on the same machine, depending on its internal state at the given time that it ran. So we use the following criterion: the number of steps required relative to the input.

Two given computers may differ in how quickly they can run an algorithm depending on clock speed, available memory and so forth. They will however tend to require approximately the same number of instructions and we can measure the rate at which the number of instructions increases with the problem size.

This is what the term asymptotic runtime means: the rate at which the runtime of an algorithm grows compared to the size of its input. For precision and accuracy we use the worst case scenario as the benchmark.

So, more formally:

The efficiency of algorithm A can be contrasted with the efficiency of algorithm B based on the rate at which the runtime of A grows relative to its input, compared to the same property in B (assuming the worst possible performance).

We will find that for the runtime of some algorithms, the size of the input does not change the execution time. In these cases, the runtime is proportional to the input quantity. For other cases, this will not hold true: we will see that there is a relationship between input size and execution time such that the length of the input affects the amount of work that needs to be performed on each item at execution.

Note

From now on we will use the word 'input' to denote the data that the algorithm 'receives' (in most cases we will conceive this as an array containing a certain data type) and 'execution' to denote the computation that is applied by the algorithm to each item of the data input. Rephrasing the above with these terms we can say that 'algorithmic efficiency' is a measure that describes the rate at which the execution time of an algorithm increases relative to the size of its input.

Linear time complexity

Before we can introduce the famous 'Big O' notation to represent algorithmic complexity, we first need a concrete example of a specific complexity which we will then express using formal notation. We'll start with linear time as it is the most intuitive to grasp.

Let's take a simple function that takes a sequence of integers and returns their sum:

function findSum(array) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total = total += arr[i];
  }
  return total;
}

The input of this function is an array of integers. It returns the sum of the integers as the output. Let's say that it takes 1ms for the function to sum an array of two integers. If we passed in an array of four integers, how would this change the runtime? The answer is that it would take twice as long. Given that the time it takes to execute findSum doesn't change (it's always the same give or take fractional variances, regardless of whether it's summing 2, 5 or 8, 1000), we can say that the runtime is as long as the number of integers we pass in. A more general way to say this is that the runtime is equal to size of the input. Thus, for algorithms of the class of which findSum is a member: the runtime is (roughly) proportional to the number of items to be processed.

We've used an entirely arbitrary value of the time it takes our function to sum two integers: 1ms. This is just so we have a quantity to work from, the actual figure is immaterial to the maths underpinning this time complexity. Using this value, we can build the following data set:

Length of inputRuntime (ms)
21
42
63
84
106

If we plotted the data on a graph it becomes clear that it is equivalent to a linear distribution:

Algorithms which display this distribution are therefore called linear algorithms and this is sometimes expressed by saying that they "run in linear time".

The crucial point is that the amount of time it takes to sum the integers does not increase as the algorithm proceeds and as the input size grows. This time remains the same. If it did increase, we would have a curve on the graph. This aspect remains constant, only the instructions increase.

We can now introduce notation to formalise the algorithmic properties we have been discussing.

Big O notation

To express how algorithms that run in linear time work formally, we say that:

It takes some constant amount of time (C) to sum one integer and n times as long to sum n integers

The algebraic expression of this is cn : the constant multiplied by the length of the input. In algorithmic notation, the reference to the constant is always removed. Instead we just use n and combine it with a 'big O' which stands for 'order of complexity': O(n)

If we have an array of four integers being passed to findSum as input we could technically express it as O = c * 4 or O(4), but we don't because we are interested in the general contour of the runime not the specific details. The execution time remains constant, it won't change as n increases.

So a linear algorithm is expressed algebraically as O(n) which is read as "oh of n" and means **with an order of complexity equal to (some constant) multiplied by n_.

Applied, this means that an input of length 6 (n) where execution time is constant (c) at 1ms has a total runtime of 6 x 1 (6ms). O(n) is is just a formal way of saying that the runtime grows on the order of the size of the input.

Important!

We should remember that when we talk about the execution runtime being constant at 1ms, this is just an arbitrary placeholder. We are not really bothered about whether it's 1ms or 100ms: 'constant' in the mathematical sense doesn't mean a unit of time, it means 'unchanging'. We are using 1ms to get traction on this concept but the fundamental point being expressed is that the size of the input doesn't affect the execution time.

Constant time

Constant time is another one of the main classes of algorithmic complexity. It is expressed as O(1). Here, we do away with n because with constant time we are only ever dealing with a single execution so we don't need a variable to express nth in a series or 'more than one'. Constant time covers all singular processes, without iteration.

An example in practice would be returning an array index value:

function returnFifthIndex(array) {
  return array[4];
}

Regardless of the size of the array, it is only ever going to take one step, or constant times one. On a graph this is equivalent to a flat line along the time axis. Since it only happens for one instance, it doesn't persist over time or have multiple iterations.

If you think about it, there is a clear logical relationship between constant and linear time: because the execution time of a linear algorithm is constant, regardless of the size of n, each execution of O(n) is equal to O(1). Thus O(n) is simply O(1) iterated. At any given execution of an O(n) algorithm n is going to be equal to 1.

Quadratic time

With the examples of constant and linear time, the total length of the input does not change the amount of work that needs to be performed at each execution, but this only covers these subsets of algorithms. In cases other than O(1) and O(n), the length of the input can affect the amount of work that needs to be performed at execution. The most common example of this scenario is known as quadratic time, represented as O(n^2).

Let's start with an example.


const letters = ['A', 'B', 'C'];

function quadratic(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length j++) {
      console.log(array[i]);
    }
  }
}

This function takes an array . The outer loop runs once for each element of the array that is passed to the function. For each iteration of the outer loop, the inner loop also runs once for each element of the array.

When we call quadratic(letters) we get the following:

A A A B B B C C C

Here, n (the size of the input) grows at a rate of n^2 or the input multiplied by itself. Our outer loop (i) is performing n iterations (just like in linear time) but our inner loop (j) is also performing n iterations, three js for every one i . It is performing n iterations for every nth iteration of the outer loop. So runtime here is directly proportional to the squared size of the input data set. As the input array has a length of 3, and the inner array runs once for every element in the array, this is equal to 3 x 3 or 3 squared (9).

If the input had length 4, the runtime would be 16 or 4 x 4. For every execution of linear time (the outer loop) the inner loop runs as many times as is equal to the length of the input.

This is not a linear algorithm because as n grows the runtime increases as a factor of it. Therefore the runtime is not growing proportional to the size of the input, it is growing proportional to the size of the input squared.

Graphically this is represented with a curving line as follows:

We can clearly see that as n grows, the runtime gets steeper and more pronounced. This trend will increase so long as n grows.

Logarithmic time

With algorithms that run in logarithmic time, n grows as a logarithmic proportion. Most simply, a logarithm is just the inverse of exponentiation. The following logarithm log2 8 = 3 can also be expressed using exponents: log^3 = 8.

Every logarithm has a base. Usually this is 10 but in the case of algorithms we use base 2 (given that computers use the binary number system). The logarithm of a number, using base 2, is roughly a measure of how many times you can divide a target number by 2 before you get a value that is less than or equal to 1. If we apply this to the earlier example of log 8, the process is as follows:

  • 8 / 2 = 4 (count = 1)
  • 4 / 2 = 2 (count = 2)
  • 2 / 2 = 1 (count = 3)

So we can divide 8 by 2 three times before reaching 1, thus log8 in base 2 is 3.

What does this mean in the context of n? Well there is a functional overlap with the way you derive a logarithm and algorithms that run in logarithmic time. Algorithms of the class O(log n) are often dubbed "divide and conquer" methods because they work by breaking the input into subsets and repeating a linear process until the target is met. For example the Quick Sort and Binary Search sorting algorithms leverage logarithmic time, so too do recursive functions.

In practice this means that during the runtime of logarithmic algorithm time goes up in a linear distribution and n increases exponentially. Effectively this means, compared to linear and quadratic time, more input can be executed faster since time is slower than the growth of n. This is demonstrated by the graph below which shows the distribution levelling of around the 100ms mark.

It's worth noting that this distribution is a mirror-image (along the x-axis) of the quadratic distribution. This bears out the point that log-based algorithms work as the opposite to exponentiation.

Let's consider a concrete example of a log-time algorithm. Say we have a sorted array of integers of length n. We want to write a search function that accepts an integer as an argument and returns the index where this value is located in the array.

The inefficient, O(n) method (known as linear search) would be to iterate through every element in the array until the first integer matching the function argument is found. No big deal when you have an array of ten elements, but much more problematic with an array of 10^8 integers. The more efficient logarithmic approach (known as binary search) is to divide the array into sections and check the range of each section against the integer we are seeking.

Here's our array, and let's say we are looking for 16

1, 2, 3, 5, 8, 10, 12, 15, 16, 28

There are ten elements so we would first proceed by splitting it into two equal groups of five:

1, 2, 3, 5, 8

10, 12, 15, 16, 28

Then we ask: is the value we are seeking greater than the highest number in the first split? We're looking for 16 so the answer is "yes". Therefore we discard the first group. Now we are left with:

10, 12, 15, 16, 28

Now we ask the same question. This time, the answer is "no": 28 is not lower than 16. This tells us our answer lies within the second split. At this point we can then apply a linear method to iterate through the five elements of the second split until we find 16. By applying a single split at the outset, we have literally halved the size of (n). This halving process is reflected in the flattening of the log distribution in the graph above. And if our second answer was "no", we would just need to split the second split into a further two sub-splits and repeat until we found our target number. At each step we are 'dividing' and then 'conquering' the data set.

Reducing complexity to the general case

We mentioned earlier in the discussion of linear time that the difference between O(4) and O(400) say, is not that significant when comparing classes of algorithms. Let's expand on that with some examples.

When we talk about big O we are looking for the most general case, slight deviations, additions or diminutions in n are not as important as the big picture. We are looking for the underlying logic and patterns that are summarised by the classes of O(1), O(n), O(n^2) and others.

Take a look at the following function:

function sumAndAddTwo(array) {
  let total = 0;
  for (let i = 0; i < array.length; i++) {
    total += array[i];
  }
  total = total += 2;
}

The formal representation of the two parts of the function would be O(n) + O(1) [1]. For an array of length 4, we could express this as O(4) + O(1) = O(5). But we might as well just say O(n) since the difference between 4 and 5 executions is marginal and we are interested in the general pattern, the relation of n to execution time overall. This doesn't change in linear or constant time, so we reduce to the common denominator which is O(n).

Similarly with this function:

function processSomeIntegers(integers){
    let sum, product = 0;

    integers.forEach(function(int){
        return sum += int;
    }

    integers.forEach(function(int){
        return product *= int;
    }

    console.log(`The sum is ${sum} and the product is ${product}`);
}

It might appear to be more complex than the earlier summing function but it isn't really. We have one array (integers) and two loops. Each loop is of O(n) complexity and does a constant amount of work. If we add O(n) and O(n) we still have O(n), not O(n^2). The constant isn't changed in any way by the fact that we are looping twice through the array in separate processes, it just doubles the length of n. So rather than expressing this as O(n) + O(n), we just reduce it to O(n).

When seeking to simplify algorithms to their most general level of complexity, we should keep in mind the following shorthands:

  • arithmetic operations always take constant time
  • variable assignment always takes constant time
  • accessing an element in an array by index or an object value by key is always constant
  • in a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

With this in mind we can break down the findSum() function like so:

Annotated function

This gives us: O(1) + O(1) + O(1) + O(n) + O(n) which can just be reduced to O(n).

Here are some examples of other simplifications:

Long formReduced
O(n + 10)O(n)
O(100 * n)O(n)
O(25)O(1)
O(n^2 n^3)O(n^3)
O(n + n + n + n)O(n)

Space complexity

This post focuses only on time complexity but it is important to know that the efficiency and relative complexity of algorithms is also assessed in terms of space. Here 'space' means how much random access memory is utilised during the runtime of the algorithm. When we think in terms of space we are interested not in, for example, how many times the function executes but in where and how the data is stored: how many variables are initialised, how many elements the arrray holds, the difference in memory consumption between list and graph data structures and so forth. Space complexity is also expressed in terms of Big O notation.

Notes

  1. In fact there is more going on in sumAndAddTwo(). In addition to looping through array and adding to total:

    • We are assigning 0 to total once (O(1))
    • We are increasing i by 1 on each iteration (O(n))
    • We are updating the value total to the sum oftotal plus array[i] on each iteration (O(n)).

    But again, we merge the specifics into the general case and reduce O(n) + O(n)+ O(1) + O(1)... to O(n)