Space complexity of a function which builds n-sized array after calling it

Question

I'm trying to learn how to estimate memory complexity of certain functions. And now I'm having a problem with one peculiar case.

So let's say we're building a function, something like this:

let f x = (fun x -> x :: [1;2;3]);;

And we're never calling this function, we're only composing it with another function at some point using this:

let compose f g x = f (g x);;

So the question is - how much space does f require before calling it and after calling compose on it? In order to make this question more general, when f builds n-sized array, but is not called, does it still take O(n) space or maybe it starts taking this space after calling it?

Answer 1

First note that [1;2;3] is an immutable list, not an array. This has an impact on your space calculations because lists can share structure. Second, for simplicity I'll discuss things in terms of "conses", two-argument list constructors that take three words of storage - in reality OCaml programs are written in terms of constructors of many arities.

Looking at f, it generates one fresh cons per invocation, and references a list containing three constant conses. Assuming that constant conses are allocated statically (with ocamlopt they are) we can use these observations to write an rough equation for space usage.

conses_used = 3 + 1 * reachable-results-of f

"Reachable result" means a value that is produced by f and still visible within the program. Unreachable parts are ignored as the GC will reclaim them.

When making this sort of estimation, make sure you understand that a cons is constant when all of its parts are constant (and no part is mutable). If the tail of a cons is a list with any non-constant part, then the cons is non-constant.

That is, in the following

let f x = [1;2;3;x]

there are no constant conses - all four will be allocated fresh each time through f.