G.R.G. writes: years ago, we got to program on the original Macintosh. Believe it or not, it had really impressive speed with its 8MHz CPU. And then we inherited a programmer named Sheena. Her degree was in Cinema. We needed programmers. Sheena is what we got.

Generally, we tried to parcel out the simplest part of every project for Sheena. In this one big project, we needed a procedure that would read entries out of a Help file. So we gave that job to Sheena. The spec was: "Write a procedure that returns the N'th line of the help file."

Well, a few weeks later she gave us the code. It did exactly what was spec'd:

  • The first line showed up immediately.
  • The second line showed up almost immediately.
  • The third line, took a noticeable fraction of a second.
  • The fourth line took several seconds.
  • The fifth line, over a minute.
  • The sixth line, we hit the reset switch before it came up.

How could the code be so slow? It was very close to this:

procedure ReadLine( Index: integer; var Line: String );
begin
    reset( HelpFile );  CurPos := 0;
    for i := 1 to Index do  ReadL( Line );
end;


procedure ReadL( var Ans: String );
var Ch: char;
begin
     Ans := '';
     repeat
       ReadC(  Ch );
       Ans := Ans + Ch;
     until Ch = #13;
end;


procedure ReadC( var AnsCh: Char );
begin
    reset( HelpFile );
    for i := 1 to Curpos do Read( HelpFile, AnsCh );
    CurPos := CurPos + 1;
end;

That's right, to read line X, you first read all the previous lines. To read each line, you read each character. To read each character, you read all the characters before it. It works ... as about an O(4) algorithm.