Big-O Notation in Purely Functional Languages – Explanation and Examples

algorithm-analysisalgorithmsbig ofunctional programmingpure-function

Is it still relevant?

Instead of

var result = new List<int>();
for (var i = 0; i < prev.Count; ++i)
{
    result.Add(prev[i] * 2);
}

where the result.Add, prev[i], and * 2 instructions are executed 10 times (and then all their subinstructions, plus the instruction overhead for calling a subroutine)…

What about in a functional language?

map (*2) prev

How is the complexity calculated for this? Obviously, each call to a subroutine adds another instruction, but there are no "steps" to measure.

Best Answer

There is no fundamental difference. The function map has O(n) complexity, because it iterates over a list of size n and applies an operation to each element.

The loop which is explicit in your first example just happens inside the map function. A typical implementation of map could be: 

map f [] = []
map f (x:xs) = f x : map f xs

Here it is easy to see that one operation is performed for each item in the list. The implementation uses recursion rather than looping, but in any case one operation is performed per item in the list, so the complexity is O(n) either way.

Related Topic