In computer science, asymptotic analysis is the process of determining the computational complexity of algorithms as the input size increases. It is used to describe the performance of an algorithm in terms of the amount of time or space required to run it.
There are three common ways to represent the asymptotic complexity of an algorithm:
In this post, we will take a look at each of these notations and how they can be used to describe the asymptotic complexity of algorithms.
Big-O notation is used to describe the worst-case scenario of an algorithm. It gives an upper bound on the asymptotic complexity of an algorithm.
For example, consider the following algorithm for finding the maximum element in an array:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
The worst-case scenario for this algorithm is when the maximum element is at the end of the array. In this case, the algorithm will take n
steps, where n
is the size of the array. Therefore, the asymptotic complexity of this algorithm is O(n).
Big-O notation is often used to describe the asymptotic complexity of algorithms in terms of the input size. For example, the asymptotic complexity of the findMax algorithm above is O(n), where n is the size of the input array.
Big-Θ notation is used to describe the asymptotic complexity of an algorithm in the best and worst cases. It gives a tight bound on the asymptotic complexity of an algorithm.
For example, consider the following algorithm for finding the maximum element in an array:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
The worst-case scenario for this algorithm is when the maximum element is at the end of the array. In this case, the algorithm will take n
steps, where n
is the size of the array. The best-case scenario is when the maximum element is at the beginning of the array. In this case, the algorithm will take 1 step. Therefore, the asymptotic complexity of this algorithm is Θ(n).
Big-Θ notation is often used to describe the asymptotic complexity of algorithms in terms of the input size. For example, the asymptotic complexity of the findMax algorithm above is Θ(n), where n is the size of the input array.
Big-Ω notation is used to describe the best-case scenario of an algorithm. It gives a lower bound on the asymptotic complexity of an algorithm.
For example, consider the following algorithm for finding the maximum element in an array:
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
The best-case scenario for this algorithm is when the maximum element is at the beginning of the array. In this case, the algorithm will take 1 step. Therefore, the asymptotic complexity of this algorithm is Ω(1).
Big-Ω notation is often used to describe the asymptotic complexity of algorithms in terms of the input size. For example, the asymptotic complexity of the findMax algorithm above is Ω(1), where n is the size of the input array.
In this post, we have seen how asymptotic analysis can be used to describe the computational complexity of algorithms. We have also seen how the three common ways to represent the asymptotic complexity of an algorithm are Big-O notation, Big-Θ notation, and Big-Ω notation.