Algorithmic Complexity in Python ⋆ integralist

Introduction

In this post we’re going to review some different algorithmic time complexities. Let me begin by clarifying, when I say ‘algorithm’ I mean: ’logic written in code’ and when I say ‘operation’ I mean: ‘a unit of code was evaluated’, and that operation could be something as simple as x + y.

But before we get into it... time for some self-promotion 🙊

Asymptotic Analysis

Asymptotic analysis is the computing of an algorithm’s running time, and there are actually a few different variations that allow us to measure different aspects of that running time:

Big Omega: represents the lower bound.
Big Theta: represents both the lower and upper bounds.
Big O: represents the upper bound.

We’re interested in the last notation in that list (Big O notation) and what the various algorithmic complexity symbols mean when applied to simplified implementations of specific algorithms written in Python.

The reason for selecting Big O over other notations is that it’s the most relevant for performance analysis, as it helps us to understand the worst case behaviour.

Note: a fantastic ‘quick’ reference for Big O notation is bigocheatsheet.com, but also Python documents the time complexity associated with its various builtin functions (which is super useful).

Measuring Algorithmic Performance

When measuring the performance of an algorithm we’re interested in how the increase in input size will affect the growth rate of operations required, and this attribute is typically referred to as the algorithm’s ’time complexity’.

There are two types of complexity we might be interested in (both dependant upon the length of the input to be processed):

time: quantifies the amount of time taken by the algorithm.
space: quantifies the amount of memory used by the algorithm.

Note: the Big O notation used to describe these complexities is telling us the ‘growth rate’ of a function, which is typically referred to as the ‘order of the function’ (hence the ‘O’ in Big O).

Orders of Complexity

Good:
- O(1)
- O(log n)
- O(√n)
OK:
- O(n)
Bad:
- O(n log n)
Awful:
- O(n^2)
- O(2^n)
- O(n!)

Note: when writing a logarithm you are expected to specify the base: log 2(n) but with Big O notation you typically omit the two, resulting in: O(log n).

Growth Types

O(1): constant time
O(Log n): logarithmic time
O(√n): square root time
O(n): linear time
O(n Log n): linearithmic time
O(n*n): quadratic time (squared)
O(n^2): polynomial time
O(2^n): exponential time
O(n!): factorial time

Constant Time

An algorithm has ‘constant time’ when the number of operations doesn’t change as the number of elements increase.

l = []
l.append(1)
len(l)  # 1

l = list(range(1000))
len(l)  # 1000
l.append(1)
len(l)  # 1001

In the above example code it doesn’t matter how many elements are contained with the list (l). Regardless of whether we append a new element to a list consisting of one element or a thousand elements, the time complexity is O(1) constant time.

Similarly for acquiring the length of a list len(l), regardless of whether the list has one element or a thousand, the time complexity stays constant time.

Logarithmic Time

An algorithm is ’logarithmic’ when the number of operations decreases by a specific factor with each step.

Consider an algorithm for searching a specific element from a given input:

def binary_search(l, item):
    first = 0
    last = len(l)-1
    found = False

    while first<=last and not found:
        midpoint = round((first + last)/2)
        if l[midpoint] == item:
            found = True
        else:
            if item < l[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1

    return found

input = [0, 1, 2, 8, 13, 17, 19, 32, 42,]

print(binary_search(input, 3))   # found: False
print(binary_search(input, 13))  # fount: True

The algorithm used here is known as a ‘binary search’ and only works when the given input is sorted/ordered. It works on the principle of dividing the range of elements to be searched by two.

This algorithm fits the requirements of logarithmic time complexity because instead of iterating over the entire input list, we actually shorten the input by half on each ‘step’ of the algorithm.

Note: I discuss binary search in more detail in an older post.

Square Root Time

An algorithm has ‘sqrt’ (or √) time complexity when the number of operations increases dependant on the number of primes under the square root of the given number.

Consider an algorithm for checking if a number is a prime. This would have square root time complexity:

def is_prime_number(x):
    if x >= 2:
        for y in range(2,x):
            # if x divides with zero remainder (i.e. equal to bool False)
            if not (x % y):
                return False
    else:
        return False
    return True

Linear Time

An algorithm is ’linear’ when the number of operations increases linearly with the number of elements.

Consider an algorithm for searching a specific element from a given input:

def search(x, input):
    for i in input:
        print(i)
        if i == x:
            print('found element')
            return

search(5, range(10))

This example search function will loop over every element until it finds the number 5, resulting in it having O(n) linear time complexity. Meaning: if the input range changes from 10 to 1000, then the number of operations (i.e. loop iterations) increases linearly with it.

The worst case scenario is if x happens to be a number that doesn’t exist in the given input. We would have to iterate over the entire input before we realized the number didn’t exist.

Note: a much better algorithm to use (if the input was guaranteed to be ordered/sorted) would be a binary search.

What’s interesting to keep in mind is that there are algorithms that are slower still than the example we’ve given above but are still considered to be ’linear time’ (e.g. O(n)). Consider a collection of ten items that you loop over twice! That’s twice as many operations as our initial example but it’s still O(n) and not something like O(n*2).

Why is that? Well, it stems from how you calculate algorithmic complexity (see my blog post on the subject). But in essence the calculation starts off very explicit until you identify which portion of the algorithm is the ‘dominant’ (e.g. as the size of the input grows, which part of the algorithm gets worse). In the case of O(n*2) the ‘constant’ value is 2, but if the collection size changed from 10 to 1000 then (that being the n part) the n becomes the ‘dominant’ portion of the algorithm and so we can simplify big-o to just O(n).

Linearithmic Time

An algorithm is ’linearithmic’ when the number of operations increases by the number of elements (i.e. linear time) times the result of log n (i.e. logarithmic time).

Consider the ‘quick sort’ algorithm whose implementation (below) selects a random element as the ‘pivot’ and then loops the entire input list (minus the pivot) in order to identify elements that are less than the pivot and elements that are greater than the pivot (this is the ‘reduce by half’ logarithmic principle). The function recursively calls itself passing in smaller and smaller subsets of input which are iterated over:

from random import randrange

input = [10, 5, 2, 3, 7, 0, 9, 12]

def quicksort(arr):
    if len(arr) < 2:
        return arr
    else:
        rand = randrange(0, len(arr))  # grab a random index
        pivot = arr.pop(rand)
        less = [i for i in arr if i <= pivot]
        greater = [i for i in arr if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print("sorted:  ", quicksort(input))

Note: I discuss quick sort in more detail in an older post.

Quadratic Time

An algorithm is ‘quadratic’ when the number of operations become the square of the number of elements.

Consider an algorithm whose implementation is looping over some input and then nesting another loop of that same input:

def search(input):
    for i in input:
        for j in input:
            print(f'i: {i}, j: {j}')

search(range(10))

This example search function will loop over every element in input and then for each item iterated over it’ll loop through the same top-level input collection again, resulting in it having O(n*n) quadratic time complexity.

In our example code our collection is a list of ten items. Item 1 is the initial list value 0, and for that we’ll loop again ten times. We move to Item 2 (which is the value 1) and again we’ll end up looping ten times …and so on.

This means if the input range changed from 10 to 1000, then the number of operations (i.e. total loop iterations) increases as a square of the number of elements.

Polynomial Time

A polynomial time complexity is effectively a ‘quadratic’ algorithm in the sense that with quadratic O(n*n) (where n is 10) we have a number of operations equal to 100, and if we compare that to polynomial O(n^2) (where n is 10) then again we have the number of operations equal to 100.

Now the difference comes when the exponent (2) in the polynomial equation is increased (where as with quadratic it will always be a squared number). For example, O(n^3) is also referred to as being polynominal.

Exponential Time

An algorithm is ’exponential’ when the number of operations grows exponentially with the number of elements (i.e. growth whose rate becomes ever more rapid in proportion to the growing total number or size).

Note: exponential time complexity O(2^n) is worse than polynomial O(n^2) because maths tells us that over time exponential will quickly overtake polynomial.

Consider an algorithm whose implementation is calculating fibonacci numbers (which grows exponentially relative to the calculated output).

The fibonacci numbers are calculated as the addition of the last element with the current element. The sequence itself starts at zero, so the first seven numbers in the sequence would be:

0, 1, 1, 2, 3, 5, 8

So we can see 0 + 1 = 1, then 1 + 1 = 2, then 1 + 2 = 3 and so on.

Below is a possible implementation:

def fibonacci(num):
    if (num <= 1):
       return num
    return fibonacci(num - 2) + fibonacci(num - 1)

Meaning, if we wanted the sixth number in the sequence (8) we would call our function with fibonacci(6) (as the numbers are zero indexed).

Recursive functions can be difficult to build a mental model from, so let’s attempt to pick it apart with some pseudo-logic:

# f is our fibonacci function
# the logic below is the result of calling f(3)
# the third sequence number is 2
# remembering the sequence is zero indexed
# [0] = 0, [1] = 1, [2] = 1, [3] = 2, [4] = 3, [5] = 5, [6] = 8

f(3):
  3 - 2 = 1
  3 - 1 = 2
  f(1) + f(2)

  f(1) = 1
  f(2) =
     2 - 2 = 0
     2 - 1 = 1
     f(0) = 0
     f(1) = 1

  1 + 1 = 2

Factorial Time

An algorithm is ‘factorial’ when the number of operations increases in line with the number of permutations associated with the number of elements.

Consider an algorithm whose implementation is calculating the factorial, i.e. the number of permutations, for a given number (this is classically known as ‘the travelling salesman’ problem):

def factorial(n):
    for i in range(n):
        print(f'iteration [{i}]: {n}')
        factorial(n-1)

The factorial function recursively calls itself, and the output of this function should be the various permutations of the given number:

There are six permutations for a number up to three (123, 132, 213, 231, 312, 321), but imagine if you wanted the various permutations of a number up to ten?

The calculation for that would yield a disastrously large number:

10*9*8*7*6*5*4*3*2*1 = 3,628,800

Hence this is the worst performing time complexity of the lot.

Note: I discuss factorials in more detail in an older post.