Thanks for the crash course on big-o notation.
My comment was merely a response to the discussion about the solution reading every line 3 times, and its rebuttal that it was really reading half the lines twice and all the lines once. I should have been more clear about it. I was inappropriately using O() to describe this effect, apparently confusing the theoretically educated among you. Yes, this problem is O(n) time and O(1) memory, discarding constant multipliers as is customary in big-o notation. > you can do it in O(1) memory and O(n) time. just take schwern's > File::ReadBackwards solution with a fix to the module so it supports > TELL. and compare the tell values to see when you have read the middle > line. then you only read the entire file once (maybe with a dup read of > the center line) which is O(n) in time. and it uses no more than 1 > buffer (actually 2) of data which is O(1) in memory no matter the size > of the file. that assumes normal size lines and not enormous ones. My point remains that you have to read the file 1 1/2 times or keep an array in memory. There is no way to use byte offsets to find the center line in a file because linebreaks are simply a special class of character, and are not distributed with any predictability. If the TELL function works on lines rather than bytes, it is because it has read through the file and figured out where the linebreaks are and created some sort of array to remember them, which I thought was against the rules. There's no way to read the entire file exactly once, keep only 1 buffer containing only the line to save, and print out the middle line, all without using any arrays. If line length is uniform, then it's O(1) time and O(0) memory. I didn't intend to start the discussion that has ensued! :) chris
