cdiggins.com

A debate is currenly raging on at reddit.com on whether a lazy map is an O(1) algorithm or not, because of my previous blog post. I was surprised that it would be controversial, and to be honest I am a little shocked at how people seem to be throwing logic overboard. Consider the Haskell program:

let prog n = head (map (* 2) [1..n])

So is the complexity of this program O(n) because it has a map in it? It is in fact an O(1) program, because Haskell doesn’t bother evaluating the map over the entire list.

There is little disagreement about that, but the confusion arises about whether the complexity analysis of the call to “map” should be considered context sensitive. The answer is that the call itself is always constant, but it affects the complexity of other algorithms that use the output later on. 

This unfortunately means complexity analysis of a lazy program is non-trivial; we have to know the precise moments of evaluation and the details. List traversal, for example, will become non-linear if we call map N times.

Here is a fun puzzle to think about, what is the complexity of the following algorithm: “construct a list by calling a lazy map function N times, where N is the length of a list. Traverse the list N times.”. What are the assumptions of your analysis? What techniques can you use to further reduce the complexity?