> O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not?

> O(n log n) algorithm can be made O(n) by replacing eager evaluation with lazy evaluation. My question is, does this count as using the same algorithm or not? I don't think anyone is claiming that it is the same algorithm. Rather, they're claiming that using lazy evaluation gives you more choice of algorithms; and one of these algorithms is faster than the best algorithm under strict evaluation. I haven't been able to download Bird et. al's paper, but I wouldn't assume it's simply "implementing the same algorithm in Haskell instead of strict ML".