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.