Time Complexity, Space Complexity, and Big O Notation

When we're writing programs we often want them to make the best possible use of available resources, especially if we're writing code for limited systems or for problems that need a lot of resources. For example:

  • Video rendering can take hours - performance improvements let businesses produce more content in less time, leading to direct cost savings.
  • Games need to take a maximum of 1/60 of a second to render a frame for the best experience.
  • An Arduino, a popular type of embedded computer, runs at 16MHz by default, which is 100x slower than a very bad modern laptop.

All programs are algorithms. When we write an algorithm on a computer we have two main things that we're concerned about: time complexity, and space complexity.

Time complexity represents the number of operations. In practical terms, this is the CPU or GPU (compute) usage of your program.

T is a function representing the time complexity of an algorithm. It maps directly onto that algorithm's structure:

array = [1,2,3,4,5]
for element in array:
    print(element)

This loop runs 5 times over an array of 5 elements. Therefore T(5) = 5.

Space complexity represents the amount of memory needed to complete the algorithm. This is the RAM, memory cache, or disk usage your system uses to evaluate the algorithm.

We can write space complexity as S.

# let array be an array of 100 elements
l = array[0]

In this case, while T(100) evaluates to 1 (because the array already exists), S(100) evaluates to 100.

The other variable involved in analysing an algorithm is n. This represents the number of items that we're running the algorithm across. For example:

array = [1,2,3,4,5] 
# n is 5
for element in array:
    print(element)

We usually express time and space complexity in terms of n, rather than directly. It's much more usual to see T(n) = n than T(5) = 5.

Depending on the algorithm or data structure which we're analysing, it's possible that there are other variables besides n. For example, a two-dimensional array has... two dimensions! We'd usually call these x and y, but for the sake of consistency we'll instead call them m and n.

Therefore the space complexity of a two-dimensional grid is mn.

Problems

  1. What's the space complexity of a three-dimensional grid?

  2. I have a stack of books. Assume I need to remove a book from the top of the stack to get to the next book. What's the time complexity of the following?

    1. I take a book from the top of the stack.
    2. I take the 20th book in the stack.
    3. I take the last book in the stack.

  3. I want to calculate the fibonacci sequence up to a given term, and I have two ways to do it:

def fibonnaci_a(term):
    last_2 = [1,1]
    if term < 3:
        return last_2[term-1]

    for i in range(2,term):
        current = last_2[0] + last_2[1]
        last_2[0] = last_2[1]
        last_2[1] = current

    return current

fib_memo = [1,1]

def fibonnaci_b(term):
    l = len(fib_memo)
    while l < term:
        fib_memo.append(fib_memo[-2], fib_memo[-1])
    return fib_memo[-1]

How much time and space do algorithms A and B use in terms of n? If they're unrelated to n, use 1 to indicate this.

Best, Worst, Average Cases

Often there's more than one run time possible. For example, if we want to find an item in a list by looking through each item in the list, we could get lucky and have it be the first item we examine: T(n) = 1

On the other hand, it could be the last item in the list: T(n) = n

We usually distinguish between the best, worst, and average cases when we're discussing the time and space complexity of algorithms.

The best case is the smallest possible one; the worst case is the largest possible, and the average is the most likely. An extreme example of this is this joke search algorithm:

array = [i for i in range(100)]

value = -1

while value != 50: 
    index = random(len(array))
    value = array[index]

The best case of this is T(n) = 1, where we find 50 on the first try. What's the worst case?

Problems

Look at this collision algorithm. It's similar to something you might see in a game.

for i, obj1 in enumerate(objects[:-1]):
    for k, obj2 in enumerate(objects[i+1:]):
        if obj1.collides(obj2): break
  1. What are the best, worst, and average time complexities of this algorithm? Assume that for 'average' the object to be collided with is halfway through the list.
  2. What are the best, worst, and average space complexities of this algorithm? Ignore objects as a component of space since it's the collection we're iterating over.

Big O Notation

Big O is the most common notation for how complex an algorithm is to run. In Big O notation we only pay attention to the term of the algorithm with the highest indice. The indice, exponent, or power is the 2 in n^2.

We can express best, worst, and average cases in big O notation.

For example:

for element in array:
    do_something()

for element in array:
    do_something_else()

This algorithm can be written as T(n) = 2n. What is it in big O?

Big O is used differently in industry to academia. In academia the following 3 symbols are used:

O(n) - The worst case. Ω(n) - The best case. Θ(n) - The average case.

However, in industry it's rare to see any symbols other than O used, and we mostly just talk about the best, worst, and average runtimes.

Common big O complexities are:

  • O(n) = log(n)
  • O(n) = sqrt(n)
  • O(n) = n
  • O(n) = n^2

Problems

  1. Express the following in big O notation:

    1. T(2n)
    2. T(n^2 + n + 10)
    3. T(nm)

  2. What is the best, worst, and average runtime of this algorithm? Write in terms of T and n first, then in big O. Assume that the average runtime is the case where the object matches in exactly half the length of the array.

mid = len(array / 2) # the index of the middle of the array

for element1 in array[:mid]: # first half
    for element2 in array[mid:]: # second half
        do_something()

Conclusion

Understanding time and space complexity and big O notation can be really helpful in cases where we want to optimise an algorithm for a specific use case. It's also common in technical interviews to either ask about or request a certain time complexity.

While there's a bit of math involved in calculating complexities, with a little practice it should be possible to derive time and space complexity from the shape of your programs without too much difficulty.