Path: utzoo!utgpu!water!watmath!clyde!att-cb!att-ih!pacbell!ames!ll-xn!mit-eddie!bbn!rochester!udel!burdvax!kleonard
From: kleonard@PRC.Unisys.COM (gvlv2!kleonard@prc.unisys.com, Ken Leonard)
Newsgroups: comp.lang.misc
Subject: Re: Poor Algorithms
Message-ID: <5713@burdvax.PRC.Unisys.COM>
Date: 8 Mar 88 13:44:31 GMT
References: <3821@ihlpf.ATT.COM> <2791@enea.se> <404@tub.UUCP>
Organization: Unisys Great Valley Laboratory, Paoli, Pa.
Lines: 25

In article <404@tub.UUCP> net@tub.UUCP (Oliver Laumann) writes:
* ...
* I have read in the (highly recommendable, by the way) paper "Hints for
* Computer System Design" by Butler W. Lampson of Xerox Palo Alto.
* ...
* A major commercial word processing system used a "FindNamedField"
* ...
* point is that this procedure ran in time O(n^2), where n is the length
* of the document!
* 
* This result was achieved by first writing a procedure "FindIthField"
* which finds the i-th field in the document.  This, of course, takes
* time O(n).  The procedure "FindNamedField(name)" was then implemented
* in the following "natural" way [quoted directly from the article]:
*    FOR i = 0 to NumberOfFields DO
*       FindIthField; IF its name is "name" THEN EXIT
*    ENDLOOP

In the best tradition of K&R.

Regardz,                                        Engineering--The Art of Science
Ken Leonard
---                                                                         ---
This represents neither my employer's opinion nor my own--It's just something I
overheard in a low-class bar down by the docks.