Re:When your data doesn’t fit in memory: the basic techniques
by johnc1231 on Monday November 11, 2019 @04:29PM
(#21509116)
Yeah, I think the above poster said O(logn) space because that's the size of the line count in bits
[ Parent
| on HN ]
Re:When your data doesn’t fit in memory: the basic techniques
by jeremysalwen on Monday November 11, 2019 @05:34PM
(#21509642)
The usual computation model includes "log n sized words", so it really is O (1). You usually are implicitly using that model, otherwise any algorithm that used pointers would have an extra log n tacked on, e.g. linked lists append would be log n not constant.