Re:Turn O(n^2) reverse into O(n)
by comex on Sunday December 15, 2013 @11:11PM
(#6912819)
No, it is not.
[ Parent
| on HN ]
Re:Turn O(n^2) reverse into O(n)
by jefffoster on Monday December 16, 2013 @03:38AM
(#6913539)
With the naive representation of a string as a list of characters [Char], it is. The only way to get to the end of the list is to recursively take the tail of the string (see the source at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...).
There's alternative representations with different trade offs, such as Data.Text
Heh... but I was referring to the example seliopou gave, which appears to be in JavaScript, and strings is [String] rather than [Char]. I think the analogy might cause more confusion than clarification.