What is Big-O notation for purely functional languages?

Question

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.

Answer 1

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.

Answer 2

Big O notation is absolutely relevant for any program which will be executed on physical hardware. As an example, Clojure is a functional programming language, and its own documentation lists the Big O notation for operations on its data structures (particularly the collections - list, vector, and map). Knowing the Big O factors for each collection will allow you to intelligently decide between lists, vectors, sets, or something else.

Incidentally, the two pieces of code you supplied do not do the same thing. The first one runs in constant time, whereas the second one is O(n) - the runtime grows in proportion to the length of prev. As an alternative, consider this:

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

This is probably O(n) relative to the length of prev - but if prev is a linked list, then (you'd need to use ElementAt, and) the code becomes O(n^2)! Whereas map (*2) prev is O(n) even when prev is a linked list.

Answer 3

First of all: this has nothing to do with "Big O". Big O has nothing to do with complexity, algorithms, programming, computer science, etc. Big O simply compares growth rates of functions. It doesn't care what the functions describe, or whether they even describe anything at all.

What you are asking about, is simply figuring out the cost (runtime cost, memory cost, whatever …) of a program. And the way you do that is exactly the same in functional languages as it is in imperative languages:

1. define what you want to measure (runtime, memory, operations, …)
2. define your machine model (Universal Turing Machine, Multi-Tape Turing Machine, Random Access Machine, λ-calculus, …)
3. define your cost model
4. identify your primitives (stores, loads, comparisons, swaps, …)
5. count them
6. Done!

Note that all of those are important. For example, as we all know, sorting is O(n log n), right? Wrong! Comparison-based sorting in a Random Access Machine Model takes O(n log n) comparisons and swaps. But there are non-comparison based sorts such as radix sort and counting sort, which only need O(n) comparisons and swaps. And there are machine models where you are only allowed to swap two adjacent elements, but not two arbitrary elements, and in that case, it can be proven, that you cannot do better than O(n²).

For example, for search algorithms, we are often interested in counting the number of comparisons. Well, it doesn't matter whether your code is pure or not, even the purest of the pure functional languages needs to do comparisons to find something. Finding something in an unsorted array takes n/2 comparisons on average, n comparisons in the worst-case, and you count those comparisons the same way regardless of whether we are talking about a functional or an imperative language.

For sorting algorithms, we are usually interested in the number of comparisons and swaps. This is where it gets interesting, because obviously in a purely functional language with a purely functional data structure, you cannot do in-situ swaps, you will always produce a new data structure with the two elements swapped. But! The same thing is true for an imperative language trying to sort a purely functional data structure.

So, in this case, the difference is not about the languages but more about the data structures. Or, you could say, we have two different algorithms, one using an immutable data structure, and one using a mutable data structure. And for the immutable data structure, maybe counting "swaps" makes no sense and you need to count something different.

When we want to be very generic, we often count "primitive operations" of some theoretical machine, such as loads, stores, pointer dereferences, and integer add and subtract. For λ-calculus, there are similar ideas, by counting the number of reductions.

In your specific example, what we are interested in, is "number of executions of the transformation operation". And that is certainly something that we can compute for both the imperative and the functional versions. In the imperative version, the "transformation operation" is the loop body. In the functional version, it is the function passed as the first argument to map.

In both cases, we don't even need Big O at all, we don't need to estimate the growth rate, because we can count exactly how often it gets executed: it gets executed exactly prev.Count times, in both cases.

However, note that your two examples aren't exactly equivalent.

Take, for example, the following C♯ code:

var result = prev.Select(el => el * 2);
// alternatively:
var result = from el in prev select el * 2;

or, in ECMAScript:

const result = prev.map(el => el * 2);

That is much more comparable to the code in your functional example, but written in an imperative language.

The different implementations of map in imperative and functional style might look something like this (all examples in ECMAScript):

// imperative style
Array.prototype.imperativeMap = function (fn) {
  const res = [];
  for (let el of this) res.push(fn(el));
  return res;
};

// naive functional style in O(n) call stack space
Array.prototype.naiveFunctionalMap = function (fn) {
  const [first, ...rest] = this;
  return this.length === 0 ? [] : [fn(first)].concat(rest.map(fn));
};

// tail-recursive functional style in O(1) call stack space
Array.prototype.tailRecursiveFunctionalMap = function (fn) {
  const mapTailrec = (ary, acc) => 
    ary.length === 0 ? 
      acc : 
      mapTailrec(ary.slice(0, -1), acc.concat([fn(ary[ary.length-1])]));
  return mapTailrec(this, []).reverse();
};

As you can see, in all cases, there are things you can count. You just need to decide what you want to count. Some things that make sense to count: number of invocations of the callback function (n in all three cases), depth of the call stack (O(1) in case #1 and #3, O(n) in case #2), size of intermediate data structures (O(n) in all three cases).

For more information, possibly more than you ever wanted to know, you could start at this Lambda the Ultimate post titled Cost semantics for functional languages, which lists several papers on, well, cost semantics for functional languages and additionally has a lively discussion in the comments section, both of the papers listed and the topic at large.

Answer 4

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.

There are steps we can measure! In Haskell, map can be defined like this:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (a:as) = f a : map f as

This is an equational definition—the definition is in the form of a set of equations, so that the value of expressions that match the pattern on the left hand side must be the same as the value of the corresponding expressions on the right hand side.

Which means that equational definitions can be read as rewrite rules for a reduction to normal form (rewriting the expression until it meets some "doneness" property, e.g., until it cannot be rewritten anymore). By sketching this process by hand we get suitable "steps" that we can measure and use to discern the worst-case time complexity of the expression. So, for example:

map (*2) [1..n]
  ==> 1*2 : map (*2) [2..n]
  ==> 0*2 : 1*2 : map (*2) [3..n]
   .
   .
   .
  ==> 0*2 : 1*2 : ... : n*2 : map (*2) []
  ==> 0*2 : 1*2 : ... : n*2 : []

As you can see, the number of steps to reach the normal form here is proportional to the length of the list. This means that map has a worst-case time complexity of O(n).

---

Our examples are in Haskell, though, which means that there is a big catch: Haskell implementations use lazy evaluation, which means that in Haskell program values are not computed unless they're actually demanded by some code that needs to consume them. Take for example the take function, which returns up to n elements from the beginning of a list:

take :: Int -> [a] -> [a]
take _ [] = []
take n (a:as) = if n <= 0 then [] else a : take (n-1) as

Now consider this expression, which takes the first element of the previous example's result:

take 1 (map (*2) [1..n])
  ==> take 1 (1*2 : map (2) [2..n])
  ==> if 1 <= 0 then [] else 1*2 : take (1-1) (map (2) [2..n])
  ==> if False then [] else 1*2 : take (1-1) (map (2) [2..n])
  ==> 1*2 : take (1-1) (map (*2) [2..n])
  ==> 1*2 : take 0 (map (*2) [2..n])
  ==> 1*2 : if 0 <= 0 then [] else map (*2) [2..n]
  ==> 1*2 : if True then [] else map (*2) [2..n]
  ==> 1*2 : []

The worst-case time complexity of this expression is O(1), in spite of the fact that map (*2) [1..n] is worst-case O(n). With eager evaluation, the complexities of evaluating subexpressions "add up"—evaluating a complex expression is generally at least as complex as evaluating its subparts. That's not true with lazy evaluation—the cost of evaluating a complex expression may be less than its subexpressions, as in my example.

One classic, fun example of that fact is this:

take 1 (sort xs)

Sorting is worst-case O(n log n) on the length of the list, but depending on how sort is implemented, in Haskell this expression could be evaluated in worst-case O(n).