3 ms·
> A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. In term of RAM this can be done an arbitrarily sma
by mytailorisrich 7y ago
> A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file.
In term of RAM this can be done an arbitrarily small buffer in the sense that this can be done by reading the file byte by byte. I.e. O(1).
Edit: For all practical purposes the line counter is also constant space.
- rongenre 7y agoYeah log(n) would be the space to hold the digits of the counter. Presumably (unless things got super-silly), this would be dominated by the buffer size for the line being read.
- dfox 7y agoThe point there is that you don’t need a buffer for whole line, you only have to find the line terminators. Something like: printf(“0: “); ln = 1; while ((ch = getch()) != EOF) { putch(ch); if (ch == EOL) { printf(“%d: “, ln); ln++; } } And I believe that original unix implementation of nl is mostly this, although with the stdio functions replaced with raw read/write.
- johnc1231 7y agoYeah, I think the above poster said O(logn) space because that's the size of the line count in bits
- jeremysalwen 7y agoThe 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.