3 ms·
>The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the numbe
by bogomipz 7y ago
>The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space"
Can you elaborate on the O(1) solution?
- xondono 7y agoNot an expert, but after reading around OP is saying you only need a constant sized buffer (that could be as little as a character deep) to read the whole file looking for line breaks. This roughly takes O(1) space (A lot of commenters are confusing time vs space requirements) but there's a little nitpick to be found, in extremely big files the line counter itself would be O(log(n)) and would dominate.
- bogomipz 7y agoI see, yes that makes sense. The conflation with time instead of space was confusing me. Thanks.