Complexity

Here is a description of how to estimate the complexity of an algorithm.

Asimptotic complexity

It’s a method that requires you to estimate the number of elementary operations we use to process \(N\) elements. It is assumed that N is large enough or tends to infinity. We usually use the notation \(O(f(N))\), where \(f(N)\) is some function of \(N\).

So if talking that complexity of the algorithm is \(O(f(N))\) it means that there is a guaranteed number \(O\) such that the considered algorithm will perform no more than \(O*N\) actions.

Examples:

• Foundry complexity \(O(N)\) - cycle that has one iteration for each of \(N\) elements;

• Quadratic complexity of the algorithm \(O(N^2)\) - cycle that has \(N\) iterations for each of \(N\) elements.

Spatial complexity

It describes how much RAM the algorithm is using.