Big O notation: Samuel’s guide
Summary:Samuel's tutorial on 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)