Exordium & Etymology
Asymptotic notation describes the runtime of an algorithm based on the increasing input size of the algorithm. Asymptotic notation is important in computer science, as it helps engineers gauge the efficiency of the algorithms they write. To get a clear understanding of asymptotic notation, the etymology of the two words can be seen below. (You can use the etymonline.com tool to dig into the history of words).
asymptotic --- "having the characteristics of an asymptote," 1670s, see asymptote.
asymptote --- "straight line continually approaching but never meeting a curve," 1650s, from Greek asymptotos "not falling together". (Wikipedia definition: an asymptote of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the x or y coordinates tends to infinity).
notation --- "explanation of a term", 1560s (this term is considered obsolete, but it actually applies here very well --- as asymptotic notation is an explanation of an algorithm's runtime). "system of representing numbers or quantities by signs or symbols", 1706 (this is more literal, as you will see --- asymptotic notation describes the runtime of algorithms using symbols).
Asymptotic notation is an interesting term. By examining the etymology of the two words, it's easier to understand that this notation describes an algorithm's limiting behavior as the input tends towards a particular value or infinity*.* When thinking about the runtime of algorithms, it is vital to think about and determine how long the algorithm takes and how fast a function grows with the input size.
Asymptotic notation focuses on an algorithm's growth rate and simplifies the function to the most important part by getting rid of the less important factors. This means that asymptotic notation drops coefficients, constants, and low-order terms that take away from the rate of growth of the runtime. It only focuses on the parts of the algorithm that affect the growth rate, specifically the growth of n --- or the input of the function.
So how does one actually apply asymptotic notation? There are three main forms of asymptotic notation, which are all covered in this post:
- Big-Θ notation (theta)
- Big-O notation (oh)
- Big-Ω notation (omega)
The different types of function growth rates are also covered down below.
The Big Three
Big-Theta Notation
Big-Theta, Big-Θ, or simply Theta measures the runtime of an algorithm, or function, by bounding it between upper and lower bounds.
When saying that the runtime of a function is Θ(n), it means that once n gets large enough, the runtime is at least k1 * n and at most k2 * n. n has to be bound between this lower and upper value once n gets big enough.
When a function uses Big-Theta Notation, it is said to be asymptotically tight bound. This means that it focuses on large inputs of n, and the runtime is bound within a lower and upper value.
Big-O Notation
Big-O measures the runtime of an algorithm, or function, by bounding it with an upper bound. This is like saying, "the runtime grows at most this much, but it could grow more slowly."
When saying that the runtime a function is O(n), it means that once n gets large enough, the running time is at most k *f(n) for some constant k.
Big-O notation is used for asymptotic upper bounds, as it bounds the growth of the runtime from above.
Big-Omega Notation
Big-Omega, Big-Ω, or simply Omega measures the runtime of an algorithm, or function, by bounding it with a lower bound. This is like saying, "the runtime is at least this much."
When saying that a function's runtime is Ω(n), it means that once n gets large enough, the running time is at least k *f(n) for some constant k.
Big-Omega is used for asymptotic lower bounds, as it bounds the growth of the runtime from below.
Comparing Function Growth
Functions grow at different rates, and it is important to know how to differentiate between these rates in order to build efficient software systems. The four different growth rates covered here are constant, linear, polynomial, and exponential.
Constant: A function has constant growth if its output does not change based on its input. You can identify constant functions as they have no n in their expression.
Eg. 5 and 5000
Linear: A function has linear growth if its output increases linearly with the size of its input. Linear functions are those where n is never increased to a power, or used as a power. n¹ is okay.
Eg. 5n and (5/3)n
Polynomial: A function has polynomial growth if its output increases according to a polynomial expression. Polynomial functions are those where n is raised to some constant power.
Eg. 5n³ and 5n²
Exponential: A function has exponential growth if its output increases according to an exponential expression. Exponential functions are those where a constant is raised to some expression involving n.
Eg. 5^n and (5/2)^n
Keep asymptotic notation in mind when analyzing and writing algorithms. It can be looked at as a framework that guides engineers to write efficient code, and we all know how satisfying writing efficient code is. To learn more about asymptotic notation, algorithms, and computer science --- check out Khan Academy's Computer Science course.
Top comments (0)