Big O notation (and its companions)



Summary:A short guide to big O notation and other asymptotic notation (little o, big theta, big omega, little omega).
Topics: Complexity, data structures, algorithms, analysis
Slides: link (pdf)

References
  • D. E. Knuth, "The art of computer programming, vol. 1: fundamental algorithms", 3rd Ed. (1997)
  • P. Bachmann, "Die analytische Zahlentheorie" (1894)
  • E. Landau, "Handbuch der Lehre yon der Verteilung der Primzahlen" (1904)
  • D. E. Knuth, "Big omicron and big omega and big theta", ACM Sigact News 8.2 (1976)
  • T. Cormen et al., "Introduction to algorithms", Chap 3.2, MIT press (2022)
  • D. E. Knuth, "Big omicron and big omega and big theta", ACM Sigact News 8.2 (1976)
  • P. Black, "Ω" in "Dictionary of Algorithms and Data Structures", https://xlinux.nist.gov/dads/HTML/omegaCapital.html (accessed 09-2022)
  • L. McCann, "Asymptotic Notation: O, o, Omega, omega and Theta", http://www2.cs.arizona.edu/classes/cs345/summer14/files/bigO.pdf (2009)