>A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. 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.
I guess I'm misinterpreting the task, because I'm having trouble seeing how it's possible to access each line in a file without it being O(n) at a minimum. I understand O(log n) to mean that not every data point is "accessed" due to the way the data structure is organized, lines of a file in this case, but to me it appears that not every line would be prepended with a number. My instinct is that there's a lot going on with new lines/line breaks in files that I'm not aware of, so I'd really appreciate any reading material on the subject to help me better understand this. Thanks!
Good point, I was thinking in terms of time complexity rather than space, but the title clearly is in reference to memory. I guess that explains my confusion!
I made the same mistake at first, had to reread the post. I'm so used to seeing Big O notation used for time that I guess my eyes just passed over the word "space".
I guess I'm misinterpreting the task, because I'm having trouble seeing how it's possible to access each line in a file without it being O(n) at a minimum. I understand O(log n) to mean that not every data point is "accessed" due to the way the data structure is organized, lines of a file in this case, but to me it appears that not every line would be prepended with a number. My instinct is that there's a lot going on with new lines/line breaks in files that I'm not aware of, so I'd really appreciate any reading material on the subject to help me better understand this. Thanks!