Subject: Re: Short question: the letter n
From: Erik Naggum <>
Date: 2000/04/26
Newsgroups: comp.lang.lisp
Message-ID: <>

* "Scott L. Burson" <>
| My understanding has always been that it was intended to suggest
| operations that ran in linear time ("O(n)").

  time to scratch your understanding...

| This doesn't really make sense, because REVERSE, and (I think, off
| the cuff) most of the other consing versions of these operations
| also run in linear time -- it's just a much longer linear time
| because of the cost of first creating and later GC-ing the new
| conses.

  you're quite mistaken on this, too.  the non-consing versions do not
  (necessarily) run faster for a number of really hairy reasons.  they
  don't cons.  that's all.  GC'ing dead objects doesn't take time in a
  whole bunch of GC implementations -- e.g., it takes time to keep
  objects _alive_ from generation to generation in a generational GC.

| Whom could we ask to get the real scoop?  Guy Steele, perhaps?  John
| McCarthy?

  just trust me.  :)