Asymptotic notation and growth¶
Part 3 of the course, volume 3 of the lecture notes. How the functions of a natural variable that count the steps of an algorithm are compared: the asymptotic notations Theta, big O, Omega, little o and omega, their properties and the limit criterion; then the families of increasing functions (logarithms, powers, exponentials, factorial), the hierarchy of infinities and the comparison of orders of growth written with the symbols. Limits and functions of a natural variable are taken from the course of Mathematical Analysis 1.
-
9. Asymptotic notation
\(\Theta\), \(\bigO\) and \(\Omega\) notations · \(o\) and \(\omega\) notations · Limits and asymptotic notations · Relational properties of asymptotic notations · …
-
10. Asymptotic growth
Families of increasing functions of a natural variable · The hierarchy of infinities · Comparison of orders of growth