On Thu, 29 Nov 2001, Yanick wrote:
> On Thu, Nov 29, 2001 at 01:34:02PM -0500, Michael G Schwern wrote: > >>> Yesterday, I saw an interesting related exercise. Write a program that >>> reads the lines from a file and outputs the middle line. The kicker is >>> that you can't use arrays. > > > > I'll interpret that as O(1) memory, O(n) time. You can't do it in O(1) memory and O(n) time. There's a time/memory tradeoff. At line m, you have to store m/2 lines in memory if you use O(n) time, if the file stops anywhere between m and m*2 (which you don't know.) If you elect to use O(1) memory, then you have to use O(1.5*n) time, as the already submitted examples do. It seems silly to try to use O(n/2) memory if you aren't allowed to use an array. chris
