On Thu, Nov 29, 2001 at 11:34:24AM -0800, 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.) > > If you elect to use O(1) memory, then you have to use O(1.5*n) time, > as the already submitted examples do.
O(1.5*n) time is O(n) time. Constant factors are irrelevant in Big-O notation. Ronald
