Big Omicron and Big Omega and Big Theta

Knuth, D. E. (1976). Big Omicron and Big Omega and Big Theta. ACM SIGACT News, 8(2), 18-24.

Type

Journal article

Intellectual base

Primary research

Year

1976

Volume

8

Issue

2

Pages

18-24

DOI

10.1145/1008328.1008329

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/1008328.1008329

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Big O Notation
  • then adopted by Knuth in the 1970s as the standard vocabulary for algorithm analysis in computer science

    This sourceKnuth's note recounts the Bachmann-Landau origin of O and proposes the Omega and Theta conventions now standard in algorithm analysis.

• L-notation
  • One may write \(T(n)=O(L_n[\alpha,c])\), but the outer \(O\) and inner \(L\) do different work.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Not recorded. Neither this nor any other of the 2 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:b5b2739a03c2 · see in the full table