"Bernie Cosell" <[EMAIL PROTECTED]> writes:
> 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.
Doesn't it rather depend on the size of the line? Or doesn't that
affect the big O for memory?
--
Piers
"It is a truth universally acknowledged that a language in
possession of a rich syntax must be in need of a rewrite."
-- Jane Austen?
