Algorithmic complexity - a primer

Counting operations

While much can be said about the efficiency of implementation and programming languages (e.g. Python vs Fortran…), it is interesting to be able to compare algorithms directly. One way of doing this is to look at the number of elementary operations necessary for each algorithm to run: in many cases, less operations will be faster. Of course, there are some caveats to this (e.g. what is an *elemntary operation exaclty?) but it is a good starting point.

Suppose you must create a function that does an operation on a vector of length \(n\) (e.g. sort a list of length \(n\)). For this, you write an algorithm (some code), which is effectively a function \(f\). When you execute \(f\), a certain number of elementary operations must be performed by the computer (add, multiply, assign…). Let \(T_f\) be this number of operations for \(f\). Often, a fixed number of operations is always performed (e.g. before a loop), plus a number that is a function of the length of the input \(n\).

Let’s look at an example: suppose you want the sum of integers up to n. You could do a loop, or you could remember your high-school formulas. Let’s look at it in Python:

def sum1(n):
   tmp = 0
   for i in range(1, n + 1):
       tmp = tmp + i

   return tmp

def sum2(n):
   return (n * (n + 1)) / 2

sum1 performs \(T_1(n) = 2 + 2n\) operations: - 1 before the loop, to assign tmp - 1 in the loop definition (n + 1) - then 1 addition and 1 assign, times n loops

sum2 however only performs 1 addition, 1 multiplication and 1 subtraction, a total of 3 operations whatever the value of n. This implies that \(T_2(n) = 3\), and in fact \(T_2\) does not depend on n. Unsurprisingly, the second algorithm is much more efficient that the first.

Big-O notation

Math and computer-science people are often more concerned about orders of magnitude. When n is very small, often times the optimisation doesn’t matter much on modern hardware (if you are not a diehard code optimiser). But when n becomes large, algorithms that don’t scale well can break down spectacularly.

Big-O notation evaluates the order of magnitude of the number of operations of a given algorithm with respect to the input size \(n\). As \(n\) becomes large, anything but the fastest growing part of the function \(T\) becomes gradually negligible. Moreover, two algorithms with the same order of magnitude are said to behave similarly, whatever the multiplicative coefficient in front.

Going back to our previous example: if \(n\) becomes large, \(T_1(n)\) becomes indistinguishable from \(2n\). But what’s more, most issues you would encouter with this algorithm would arise with the same order of magnitude \(n\) even if you found a third algorithm with \(T_3(n) = n\). For this reason, algorithm 1 (the loop) is considered \(O(n)\).

These rules imply some simple comparison examples:

Like this post? Share on: Twitter ❄ Facebook ❄ Email