[jose_zap]

Interestingly, the naive solution presented in this article is O(n) thanks to laziness.

[foldr]

It’s O(n log n). If the strings contain the same letters then you end up fully sorting both lists, and there’s no magical way of doing that in O(n) time with a general purpose sorting algorithm.

The article is just saying that the best case performance improves because you don’t have to fully sort both lists in the case where the two words are not anagrams.

There are other cases where laziness works its magic in relation to sorting, though. For example, “sort the list and then take the first element” is (with a suitable implementation of ‘sort’) an O(n) implementation of “find min/max element of list” in Haskell.