3 ms·
I think (hope?) that user5994461's post was tongue in cheek. BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathemat
by mikebenfield 10y ago
I think (hope?) that user5994461's post was tongue in cheek.
BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.
- BeetleB 10y agoMathematicians used it for asymptotic expansions of mathematical expressions. Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.
- bogomipz 10y agoI didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : ) Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature. This is the source I am referring to from 1976 SIGACT News: http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron... On page 21 or page 4 of the PDF: "I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. " On page 22 or page 5 of the PDF: "The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."