23
$\begingroup$

When was big O first used in computer science and when did it become standard? The Wikipedia page on this cites Knuth, Big Omicron and Big Omega And Big Theta, SIGACT April-June 1976, but the beginning of that paper reads

Most of us have gotten accustomed to the idea of using the notation $O(f(n))$ to stand for any function whose magnitude is upper-bounded by a constant times $f(n)$, for all large $n$.

This quote indicates that the idea and notation were already in common use.

The Wikipedia page also cites math papers from the late 1800s and early 1900s, but that doesn't quite answer the question. In particular, I've heard researchers who were around back then (in the 60s and 70s, not the late 1800s) say that when asymptotic analysis was first used, some people pushed back, saying that wall clock time was a better metric. However, no one I've talked to can cite the specific papers that got pushback like this and I'd like to find evidence that can confirm or deny these stories.

Improve this question
$\endgroup$
3
  • $\begingroup$ Is the question about $O()$ notation for asymptotic analysis of functions, or about using asymptotic time complexity? I think the question is about the latter, but the first sentence (and the quote from Knuth) sound like being about the former. $\endgroup$
    – ShreevatsaR
    Dec 19, 2016 at 4:47
  • 2
    $\begingroup$ BTW, not relevant to your historical question, but a point that it is not entirely historical: Robert Sedgewick at Princeton (who incidentally did his PhD under Knuth) has in multiple talks warned against "big O" notation that he calls "theory of algorithms", preferring instead Knuth-style "analysis of algorithms" (i.e. with actual constants). See e.g. these slides (the first 21 slides). This is not quite the same as pushing back against asymptotic analysis and recommending wall-clock time, but well, sort of. And it's an important point. $\endgroup$
    – ShreevatsaR
    Dec 19, 2016 at 7:40
  • $\begingroup$ Did you read this section in Wikipedia History (Bachmann–Landau, Hardy, and Vinogradov notations)? $\endgroup$
    – drzbir
    Dec 22, 2016 at 22:04

1 Answer 1

Reset to default
3
$\begingroup$

with history questions there are typically subtle nuances and its not easy to determine a particular paper that introduced a particular concept because it tends to be spread over many contributors and is sometimes rediscovered independently when obscure early references dont necessarily disseminate (fundamental ideas are like that). but the history basically goes something like this: Landau notation is an old mathematical formalism (1894/ Bachman)[1] which was imported into CS as a "key concept" around the early 1970s. by the mid 1970s this was somewhat accepted as in your Knuth reference and Knuth himself was involved in spreading this concept.

interestingly its import into CS was probably closely related to the P vs NP vs Exptime distinctions uncovered in early 1970s which were highly influential/ heralded in the field. it was Cobham/ Edmonds who started to define the class P in early 1970s.[3] there were early proofs about Exptime and Expspace by Stockmeyer/ Meyer.[2] the Cook-Levin theorem[4] (1971) showed the core relevance of P vs NP time, immediately supported by Karp[5] (1972).

an early mathematician who worked in number theory but also on the edge of computer science was Pocklington. as in [3] it points out:

However, H. C. Pocklington, in a 1910 paper,[11][12] analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.

another early pioneer in analyzing complexity of machine-based algorithms for number theory, ie factoring, was Derrick Lehmer, professor of mathematics at University of California, Berkeley, and built/ analyzed factoring "algorithms" (sieve based implementations) as early as the 1920s and its possible he may have described something like computational complexity wrt factoring in an informal way.[6]

yet another case is a "lost" 1956 letter by Godel to von Neumann talking about complexity measurements of steps f(n) of a machine to find proofs of size n.[7]

[1] Big O notation history / wikipedia

[2] Word problems requiring exponential time. / Stockmeyer, Meyer (1973)

[3] P time class history / wikipedia

[4] Cook-Levin theorem / wikipedia

[5] Karps 21 NP complete problems / wikipedia

[6] Lehmer factoring machine/ sieve / wikipedia

[7] Godels lost letter / RJLipton

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ This doesn't appear to answer the question that was asked. The question was "What are the first computer science papers that used big-O?" An answer should identify some papers. I don't see any papers cited here that are candidates for an answer to the question. Saying "there are typically subtle nuances and its not easy to determine a particular paper" is not really an answer. And surely there was a paper that was first -- there has to be (by the well-ordering principle) -- so the question is answerable. $\endgroup$
    – D.W. ♦
    Dec 22, 2016 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.