Complexity of an algorithm

> LeekScript Tutorial

General idea

To estimate the amount of operations that a function or an algorithm will consume, it is useful to have an idea of the relationship between the size of the arguments given to it, or the size of a parameter, and the maximum number operations performed. This is called algorithmic complexity.

Let's start with a simple example: a for loop.

for (var i=0; i N, we have f(n) < K x g(n).*

Alright, there you go, I got the big words out. What does this definition actually mean? That the function f grows "no faster" than g as n increases. f can be greater than g, but the ratio of the two is always smaller than a certain number (the K of the definition). Let's apply this to code: let's take as a (mathematical) function f the maximum number of operations performed by a given piece of code, given the size of its input. We seek to find a simple function g such that f(n)=O(g(n)). It roughly amounts to measuring the greatest number of times that basic instructions will be repeated in the code (the cost of these instructions is thus swept under the carpet: it is the K of the definition).

Examples

Phew. Let's move on to examples, we will see more clearly. Let's go back to our for loop from earlier:

for (var i=0; i<n; i++){ say("I'm a carrot"); }

If we note f the maximum number of operations performed by this piece of code, we have seen that f(n) was roughly equal to 30 x n, plus the small cost of the loop. Indeed, the say instruction is repeated n times, which has a constant cost of 30 operations. We can therefore say that f is dominated by the function g(n)=n. Thus, we have f(n)=O(n). We also say that this piece of code is "in O(n)".

And the function of intersection of arrays of size n? We have seen that it roughly consumes n² x (number of push operations + cost of comparing two elements). Assuming that the push cost is constant (which is false, but I don't want to go into detail right away), we have, by setting K = (number of push operations + cost of comparing two elements ), that the cost of the intersection function is dominated by n²: we say that the intersection function is "in O(n²)".

Thus, the notation O makes it possible to measure the growth of the cost according to the size of the input: the intersection function will have a cost which grows "at the same speed" as n² (with n the size of the arrays).

Interest in Leekwars

This notion is interesting because we can often estimate quite easily an O(g(n)), and thus know if a function will start to cost very expensive when the input will increase. It is for example uti