Comment by 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.