News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by MBCook on Sunday December 15, 2013 @11:06PM (#6912797)
But strings.length is O(n), and you have to run it n times.
Re:Turn O(n^2) reverse into O(n) by comex on Sunday December 15, 2013 @11:11PM (#6912819)
No, it is not.
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

Re:Turn O(n^2) reverse into O(n) by comex on Monday December 16, 2013 @12:33PM (#6916296)
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.