Asymptotic Notations in DSA
In computer science and data structures, asymptotic notations is very useful concept. They are used to analyze the efficiency and performance of algorithms. In simple words these notations describe how the runtime or resource usage of an algorithm grows in relation to the input size.
In this tutorial we'll learn about three commonly used asymptotic notations Big O notation, Omega notation, and Theta notation.
Big O Notation
-
Big O notation, also denoted as O(f(n)), is the mostly used asymptotic notation. It used to describe the upper bound or worst-case time complexity of an algorithm.
-
It provides an upper limit on how the runtime of an algorithm grows as the input size (n) increases.
Omega Notation
-
Omega notation, also denoted as Ω(f(n)), is used to describe the lower bound or best-case time complexity of an algorithm.
-
It provides a lower limit on how the runtime grows as the input size (n) increases.
Theta Notation
-
Theta notation, also denoted as Θ(f(n)), is used to describe both the upper and lower bounds of an algorithm's time complexity.
-
It provides a tight bound on how the runtime grows as the input size (n) increases.
