Green Files

What is the complexity of an algorithm?

Day: 06/02/2022 - Time: 10:37:07

What is the complexity of an algorithm, and what are the means to measure it (Big O, Big Theta...)

The complexity of an algorithm has to do with how much time and memory that algorithm spends according to the size of its input. For example, we want to answer questions like "if my algorithm takes 1 minute to process an input of 1000 bytes, how many minutes will it take to process an input of 2000 bytes?"

A very straightforward way of calculating complexity would be to find some formula that gives the exact number of operations performed by the algorithm to arrive at the result, as a function of the size of the input. For example, in the algorithm

for(i=0; i<N; i++){ print(i); }

We could say that the time spent is:

T(N) = N*(time spent comparing i and N) + N*(time spent to increment i) + N*(time spent by a print)

However, it's a lot of work to make a super accurate account like that and it's usually not even worth it. For example, suppose we put a lot of effort into it and found that a certain algorithm takes a time

T(N) = 10*N² + 137*N + 15

In this case the quadratic term 10*N² is more important than the others because for practically any value of N it will dominate the sum total. From N ≥ 14, the quadratic term is already responsible for most of the execution time and for N > 1000 it is already responsible for more than 99%. For estimation purposes we could simplify the formula to T(N) = 10*N² without losing much.

Another point where we can simplify our formula is the constant factor multiplying the N². To predict how fast the execution time grows depending on the input it doesn't matter if T(N) = 10*N or T(N) = 1000*N; in both cases doubling the N will quadruple the execution time.

For all that, the most popular way of working with time and space complexity in algorithm analysis is asymptotic complexity, which ignores these constant factors and terms that grow more slowly. This is where the story of O-large, Θ-large and Ω-large comes in: these are notations we use to characterize an asymptotic complexity.

Let's start with the big O, which is a way to give an upper bound on the time taken by an algorithm. O(g) describes the class of functions that grow at most as fast as the function g and when we say that f ∈ O(g) we mean that g grows at least as fast as f. Formally:

Given two functions f and g, we say that f ∈ O(g) if there are constants x0 and c such that for all x > x0 there is f(x) < c*g(x)

In this definition, the constant c gives us leeway to ignore constant factors (which allows us to say that 10*N is O(N)), and the constant x0 tells us that we only care for the behavior of f and g when the N is large and the fastest growing terms dominate the total value.

For a concrete example, consider that time function f(n) = 10*N^2 + 137*N + 15 from before. We can say that its growth is quadratic:

We can say that f ∈ O(N²), since for c = 11 and N > 137 it is worth

10*N² + 137*N + 15 < c * N^2

We can choose other values for c and x0, such as c = 1000 and N > 1000 (which make the count pretty obvious). The exact value of these pairs does not matter, what matters is being able to convince yourself that at least one of them exists.

In the opposite direction from the big-O we have the big-Ω, which is for lower bounds. When we say that f is Ω(g), we are saying that f grows at least as fast as g. In our recurring example, we can also say that f(n) grows as fast as a quadratic function:

We can say that f is Ω(N²), since for c = 1 and N > 0 it is worth 10*N² + 137*N + 15 > c*N^2

Finally, Θ-large has to do with fair approximations, when f and g grow at the same rate (except for a possible constant factor). The difference between large-Θ and large-O and large-Ω is that they admit loose approximations, (for example, N² ∈ O(N³)) in which one of the functions grows much faster than the other.

Among these three notations, the most common to see is the O-big one. Usually complexity analyzes are only concerned with the worst case execution time so the upper bound given by the big O is sufficient.