News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by dmak on Sunday December 15, 2013 @10:51PM (#6912738)
How is the original (the for loop that you mentioned) O(n^2)? Isn't that O(n)? Isn't acc += strings[i] a O(1) operation?
Re:Turn O(n^2) reverse into O(n) by alok-g on Sunday December 15, 2013 @11:01PM (#6912779)
Each time strings[i] is added to acc, it may require reallocating entire acc to new memory location with more memory for the concatenated string.
Re:Turn O(n^2) reverse into O(n) by masklinn on Monday December 16, 2013 @02:07AM (#6913318)
`acc` is assumed immutable, so it has to be copied entirely on each concatenation. Copying a string is an O(n) operation.
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.
Re:Turn O(n^2) reverse into O(n) by 10098 on Sunday December 15, 2013 @10:58PM (#6912763)
not if you have to reallocate space for storing acc on each iteration