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?