[johnc1231]

Yeah, I think the above poster said O(logn) space because that's the size of the line count in bits

[jeremysalwen]

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.