News for hackers. Stuff that matters.

A comment on Big-O Misconceptions. Parent comment

Re:Big-O Misconceptions by esrauch on Monday October 15, 2012 @05:31PM (#4657258)
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.
[ Parent | on HN ]
Re:Big-O Misconceptions by mturmon on Monday October 15, 2012 @07:51PM (#4657706)
I 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...

(Parenthetically, one look at the above link and you know why Knuth was driven to write TeX.)

[ Parent | on HN ]