4 ms·
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?
by dmak 13y ago
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?
- 10098 13y agonot if you have to reallocate space for storing acc on each iteration
- alok-g 13y agoEach time strings[i] is added to acc, it may require reallocating entire acc to new memory location with more memory for the concatenated string.
- MBCook 13y agoBut strings.length is O(n), and you have to run it n times.
- comex 13y agoNo, it is not.
- jefffoster 13y agoWith 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-List.html#length 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
- comex 13y agoHeh... 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.
- deleted 13y ago[deleted]
- masklinn 13y ago`acc` is assumed immutable, so it has to be copied entirely on each concatenation. Copying a string is an O(n) operation.
- deleted 13y ago[deleted]