Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.
The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.
1) Θ Notation: The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.
A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants.
Example:
3n3 + 6n2 + 6000 = Θ(n3)
Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) beats Θn2) irrespective of the constants involved.
2) Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
Example: Consider the case of Insertion Sort.
It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2).
If we use Θ notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:
1. Worst case time complexity = Θ(n^2).
2. Best case time complexity = Θ(n).
The Big O notation is useful when we only have upper bound on time complexity of an algorithm. Many times we easily find an upper bound by simply looking at the algorithm.
3) Ω Notation: Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.
Ω Notation can be useful when we have lower bound on time complexity of an algorithm.
The best case performance of an algorithm is generally not useful, the Omega notation is the least used notation among all three.
Example: Consider the case of Insertion Sort.
The time complexity of Insertion Sort can be written as Ω(n), but it is not a very useful information about insertion sort, as we are generally interested in worst case and sometimes in average case.
The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.
1) Θ Notation: The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.
A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants.
Example:
3n3 + 6n2 + 6000 = Θ(n3)
Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) beats Θn2) irrespective of the constants involved.
2) Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
Example: Consider the case of Insertion Sort.
It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2).
If we use Θ notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:
1. Worst case time complexity = Θ(n^2).
2. Best case time complexity = Θ(n).
The Big O notation is useful when we only have upper bound on time complexity of an algorithm. Many times we easily find an upper bound by simply looking at the algorithm.
3) Ω Notation: Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.
Ω Notation can be useful when we have lower bound on time complexity of an algorithm.
The best case performance of an algorithm is generally not useful, the Omega notation is the least used notation among all three.
Example: Consider the case of Insertion Sort.
No comments:
Post a Comment