On: When your data doesn’t fit in memory: the basic te...

[mytailorisrich]

> 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 → mytailorisrich]

Yeah 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 → rongenre]

The 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 → mytailorisrich]

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

[jeremysalwen → johnc1231]

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.