3 ms·
It's my understanding that the horse left the barn before Big-Theta was ever invented; Big-O was widely used even in formal papers more loosely and Big-Theta wa
by esrauch 14y ago
It's my understanding that the horse left the barn before Big-Theta was ever invented; Big-O was widely used even in formal papers more loosely and Big-Theta was only in dusty obscure text books until Knuth came along.
- mturmon 14y agoI think you're right. Moreover, the related Landau big-O notation was used in real analysis before the algorithm analysis big-O notation was in use (Landau died a month after Knuth was born, in the thirties). Related number theorists had notations for big-Omega and little-o as well, but I think big-Theta was pretty much Knuth's idea. Knuth's summary of the history of these notations is at: http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron... (Parenthetically, one look at the above link and you know why Knuth was driven to write TeX.)