CODEWITHSUNDEEP
functional-programmingruntimeocaml
Timothy Deng
Timothy Deng

Reputation: 494

Calculating Big-O time and space complexity for functional languages

I'm thinking of using Ocaml for technical interviews in the future. However, I'm not sure how to calculate time and space complexity for functional languages. What are the basic runtimes for the basic higher level functions like map, reduce, and filter, and how do I calculate runtime and space complexity in general?

Upvotes: 2

Views: 1027

Answers (1)

ivg
ivg

Reputation: 35210

The time complexity of persistent recursive implementations is easy to infer directly from the implementation. In this case, the recursive definition maps directly to the recurrence relation. Consider the List.map function as it is implemented in the Standard Library:

let rec map f = function
  | [] -> []
  | a::l -> f a :: map f l

The complexity is map(N) = 1 + map (N-1) thus it is O(N).

Speaking of the space complexity it is not always that obvious, as it requires an understanding of tail-calls and a skill to see the allocations. The general rule is that in OCaml native integers, characters, and constructors without arguments do no allocate the heap memory, everything else is allocated in the heap and is boxed. All non-tail calls create a stack frame and thus consume the stack space. In our case, the complexity of the map in the stack domain is O(N), as it makes N non-tail calls. The heap-complexity is also O(N) as the :: operator is invoked N times.

Another place, where space is consumed are closures. If a function has at least one free variable (i.e., a variable that is not bound to function parameters and is not in the global scope), then a functional object called closure is created, that contains a pointer to the code and a pointer to each free variable (also called the captured variable).

For example, consider the following function:

 let rec rsum = function
   | [] -> 0
   | x :: xs -> 
     List.fold_left (fun y -> x + y) 0 xs + rsum xs

For each element of a list, this function computes a sum this element, with all consecutive elements. The naive implementation above is O(N) in the stack (as each step has two non-tail calls), O(N) in the heap size, as each step constructs a new closure (unless the compiler is clever enough to optimize it). Finally, it is O(N^2) in the time domain (rsum(N) = (N-1) + rsum(N-1)).

However, it brings a question - should we take into account a garbage, that is produced by a computation? I.e., those values, that were allocated, during the computation, but are not referenced by it. Or those values, that are referenced only during a step, as in this case. So it all depends on the model of computation that you chose. If you will choose a reference counting GC, then the example above is definitely O(1) in the heap size.

Hope this will give some insights. Feel free to ask questions, if something is not clear.

Upvotes: 3

Related Questions