[unlivingthing]

I think you've got confused with O(n) time; that is the amount of memory that is needed and not the time required to access a particular line.

[tmh88j]

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!

[profmonocle]

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".

(My mistake obviously, the OP was very clear.)