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 );
    reset( HelpFile );  CurPos := 0;
    for i := 1 to Index do  ReadL( Line );

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

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

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.

[Advertisement] BuildMaster allows you to create a self-service release management platform that allows different teams to manage their applications. Explore how!