# Algorithm Complexity Analysis on functional programming language implementations

I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of.

An example given to me, that illustrated it further, by User @chi was:

E.g. consider the task: given $(i,x_1 ,…,x_n )$ return $x_i$ . In RAM this can be solved in $O(1)$ since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$

This makes me wonder about functional languages; From my understanding, "Functional languages are intimately related to the lambda calculus" (from a comment by Yuval Filmus on here). So, if functional languages are based on lambda calculus, but they run on RAM based machines, what is the proper way to perform complexity analysis on algorithms implemented using purely functional data structures and languages?

I have not had the opportunity to read Purely Functional Data Structures but I have looked at the Wikipedia page for the subject, and it seems that some of the data structures do replace traditional arrays with:

"Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic."

In that case, the computational model would be different, correct?

• I am definitely not an expert on this topic, but I believe I heard that 1) a lisp-like machine (with its own cost model) can simulate RAM programs with a $O(\log n)$ additional factor (this looks easy to prove), and 2) whether this factor is really needed is still an open problem. Further, it can be argued that assigning a O(1) cost to array access in the RAM model is too generous. In hardware, memory access has to traverse $O(\log n)$ gates where $n$ is the size physical memory. – chi Sep 26 '16 at 13:26
• Also keep in mind that virtually all real-world FP languages have arrays in some form, with a guaranteed $O(1)$ access time (as in imperative languages). This is typically solved adding them as a language primitive. – chi Sep 26 '16 at 13:30
• An example of a different computational model would be the number of beta reductions done on a lambda calculus term. In FP we are more so using a ram model dressed up as a lambda calculus, if that makes sense – Kurt Mueller Sep 26 '16 at 13:47
• @KurtMueller Note that we can get a lambda term of size $O(2^n)$ after only $O(n)$ bete reductions. This makes the cost model of counting the number of beta unrealistic. An arguably better one could be to weigh each step by the size of the terms at hand. Yet, this is not the only possible model: optimal evaluation of lambda terms does not apply beta in the naive way, preferring some more sophisticated graph reduction machines. In such case, counting the betas would probably be not appropriate. – chi Sep 26 '16 at 15:01
• Note that you also need to know whether your functional language is eager or lazy / strict or non-strict. I recently encountered a situation where a real-world algorithm was polynomial in Haskell (non-strict) but the naive translation to OCaml (strict) was exponential. – Eric Lippert Sep 26 '16 at 20:01