On 29 Nov 2001, at 11:34, Chris Thorpe wrote:
> 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.)
That's just not true. Consider the algorithm:
1) count the lines in the file [don't retain ANY data --- just scan
the file and count lines]
2) rewind, skip N/2 lines, read the next one
Which is unequivocally O(1) memory and O(n) time.
/Bernie\
--
Bernie Cosell Fantasy Farm Fibers
mailto:[EMAIL PROTECTED] Pearisburg, VA
--> Too many people, too few sheep <--
