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
twodimensional 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 twodimensional grid is mn
.
Problems
 What's the space complexity of a threedimensional grid?

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?
 I take a book from the top of the stack.
 I take the 20th book in the stack.
 I take the last book in the stack.

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[term1]
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
 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.
 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

Express the following in big O notation:
T(2n)
T(n^2 + n + 10)
T(nm)

What is the best, worst, and average runtime of this algorithm? Write in terms of
T
andn
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.