Ryan Ingram <ryani.s...@gmail.com> writes: > You can emulate mutation with at most O(log(n)) penalty using a map. Given > that memory is of fixed size, log2(n) <= 64, so for "real-world" programs > this becomes O(1).
I'm not sure assuming fixed size memory is a good idea for a theoretical discussion - your computer is no longer Turing complete, and one type of implementation will likely be able to fit a different set of programs in the given memory than the oher. Another nit: this is O(log(n)) of working set, not input/problem size. But I guess any algorithm must be at least O(working set size), so it's still a log factor (or less) of the algorithmic complexity. -k -- If I haven't seen further, it is by standing in the footprints of giants _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
