Asymptotic Notations - Data Structures
![DSA Problem Solving for Interviews using Java](https://www.scaler.com/topics/images/jitender_punia.webp)
Asymptotic notations in data structure are mathematical tools used to analyze the runtime of algorithms as input size grows. They enable comparison of algorithm efficiencies without manual runtime calculations, particularly beneficial for larger inputs. This article delves into different types of asymptotic notations and their application, excluding discussions on space complexity. Asymptotic notations offer crucial insights into algorithm performance, aiding in algorithm selection and optimization.
What is an Asymptotic Notation?
Asymptotic notation is a mathematical notation that is used to analyze the time complexity and the runtime of an algorithm for a large input.
For example if we want to compare the runtimes of the bubble sort algorithm and merge sort algorithm, we can use asymptotic notations to do this comparison.
In this article, we will discuss three types of asymptotic notations that are most commonly used to analyze time complexities of various algorithms. These are Big O notation (O), omega notation (Ω) and theta notation (θ).
Big O Notation (Represented as O)
Let and be two functions dependent on the input variable n. So, the function if there exists some positive constants and such that f(n) <= c.g(n) for all .
For example, let f(n) = 2n + 5.
In order to find the Big O of this function, we have to find another function such that f(n) <= c.g(n) for all where and are positive constants.
If we take and put this is the above equation, we can see that for all and . Hence, we can say that the function . But we write it as as we generally analyze an algorithm for a large input and if is large, is approximately equal to .
The comparison of the function and can also be seen in the graph given below. The function for points where .
Let us now take the example f(n) = 7(n^2) + 3.
If we take a function , we can see that it satisfy the equation given for Big O notation with and . So, we can say that the function which can be approximately written as since we are considering it only for large values of .
The Big O notation is also called as upper bound notation. For example for the above example, we can say that the upper bound of the function is .
NOTE:
For the example f(n) = 7(n^2) + 3, one may also determine the function as since it satisfies all the conditions of Big O notation. Although is the right answer for this function, we generally find the function which is closest to and satisfying the condition of Big O notation. So the most suitable answer is .
Omega Notation (Represented as Ω)
Let and be two functions dependent on the input variable . So, the function f(n) = Ω(g(n)) if there exists some positive constants and such that f(n) >= c.g(n) for all .
For example, let f(n) = 2n + 5.
In order to find the omega of this function, we have to find another function such that f(n) >= c.g(n) for all where and are positive constants.
If we take and put this is the above equation, we can see that for all n >= 0 and c = 1. Hence, we can say that the function .
The comparison of the function and can also be seen in the graph given below. The function for points where n > x.
Let us now take the example f(n) = 7(n^2) + 3.
If we take a function , we can see that it satisfy the equation given for omega notation with c = 1 and n' = 0. So, we can say that the function .
The omega notation is also called as lower bound notation. For example for the above example, we can say that the lower bound of the function is .
NOTE:
For the example , one may also determine the function as since it satisfies all the conditions of omega notation. Although is the right answer for this function, we generally find the function which is closest to and satisfying the condition of omega notation. So the most suitable answer is .
Theta Notation (Represented as θ)
Let and be two functions dependent on the input variable n. So, the function f(n) = θ(g(n)) if there exists some positive constants and such that for all .
For example, let f(n) = 2n + 5.
In order to find the theta of this function, we have to find another function such that for all where and are positive constants.
If we take and and put this is the above equation, we can see that for all and . Hence, we can say that the function .
The comparison of the function , and can also be seen in the graph given below. The function and for points where .
The theta notation is also called as tight bound notation. For example for the above example, we can say that the tight bound of the function is .
Graphical Representation for the Asymptotic Notations
Below are the graphical plots to represent the three asymptotic function (i.e. Big O notation, Omega notation and Theta notation) with respect to the input variable .
Properties of Asymptotic Notation
Here are some properties that are satisfied by the asymptotic notations that are discussed above. All these properties can be easily proved by applying the equation we discussed in each asymptotic notation's section.
General
If we have two functions and such that f(n) = O(g(n)), then for a constant , is also .
Similarly,
If f(n) = Ω(g(n)), then c.f(n) = Ω(g(n)). If f(n) = θ(g(n)), then c.f(n) = θ(g(n)).
Multiplying a constant scaler with the function will not affect any of the equations that we saw while discussing each asymptotic notation.
Transitive
If we have three functions and such that f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).
For example, if we have a function , and .
- Since , we can say .
- Also, , this means that .
Now, if and , we can conclude . This means that .
Hence, we can can say that .
Similarly,
If and , then . If and , then .
We can verify this property using the equations that we have discussed in the section of each asymptotic notation.
Reflexive
If we have a function f(n), then by default, we can write,
,
,
.
We can verify this property using the equations that we have discussed in the section of each asymptotic notation.
Symmetric
If we have two functions and such that f(n) = θ(g(n)), then we can also say that g(n) = θ(f(n)).
We can verify this property using the equation that we have discussed in the section of theta notation.
NOTE: This property only satisfies for theta notation.
Transpose
If we have two functions and such that f(n) = O(g(n)), then we can say that .
We can verify this property using the equations that we have discussed in the section of each asymptotic notation.
NOTE: This property only satisfies for Big O and Omega notations.
Conclusion
- Asymptotic notations in data structure are indispensable tools for understanding the efficiency of algorithms as input size grows.
- They enable straightforward comparison of algorithm efficiencies without the need for manual runtime calculations, especially beneficial for large inputs.
- The three primary types discussed here include Big O, Omega, and Theta notations, each offering unique insights into algorithm performance.
- Asymptotic notations are widely used in algorithm analysis and design, aiding in algorithm selection and optimization strategies.
- Various properties such as transitivity, reflexivity, symmetry, and transposed symmetry further enhance the utility and applicability of asymptotic notations in algorithm analysis.