Asymptotic Notations
Asymptotic Notations
Asymptotic notations are languages that allow us to analyze the performance of an algorithm in terms of input size. The basic idea of asymptotic analysis is to measure the efficiency of algorithms that doesn’t depend on any machine specific constants (like specific hardware, operating system, compiler, programmer etc). Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm-
Big-O Notation
Big-O Notation is an asymptotic notation for the worst case, or the longest amount of time an algorithm can possibly take to complete. It defines an upper bound of an algorithm in terms of time complexity.
Big-omega Notation
Big-omega Notation is an asymptotic notation for the best case, or the best amount of time an algorithm can possibly take to complete. It defines an lower bound of an algorithm in terms of time complexity.
Big-theta Notation
Big-theta Notation is an asymptotic notation for the average case, or the average amount of time an algorithm can take to complete. It defines an average or tight bound of an algorithm in terms of time complexity, which lies between upper bound and lower bound.
Little-o
Little-o is denoted by symbol o. Little-o notation defines an upper bound of an algorithm, that is not tight in terms of time complexity.
Little-omega
Little-omega is denoted by symbol ω. Little-omega notation defines an loose lower bound of an algorithm in terms of time complexity.