Time Complexity Of Different Sorting Algorithms

Mark as Completed

Lesson

When we analyze the time complexity of an algorithm, we usually consider three scenarios:

Best-case time complexity: The best-case time complexity is the minimum amount of time required for the algorithm to complete its task. This happens when the input is in a state that allows the algorithm to take advantage of its most efficient implementation. For example, if we were searching for an element in an array, the best-case scenario would occur if the element was found at the very first index. The best-case time complexity is denoted as O(1) (constant time complexity).
Average-case time complexity: The average-case time complexity is the amount of time required for the algorithm to complete its task, assuming that the input is randomly distributed. This is the most common scenario and is usually the one we focus on when we talk about time complexity. For example, if we were searching for an element in an unsorted array, the average-case scenario would occur if the element is located in the middle of the array. The average-case time complexity is denoted as O(n) (linear time complexity).
Worst-case time complexity: The worst-case time complexity is the maximum amount of time required for the algorithm to complete its task. This happens when the input is in a state that requires the algorithm to take the longest possible path to complete its task. For example, if we were searching for an element in an unsorted array, the worst-case scenario would occur if the element is not present in the array, and we have to search the entire array to be sure of that. The worst-case time complexity is denoted as O(n) (linear time complexity).

Let's take an example of linear search algorithm to understand these complexities better:

function linearSearch(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) {
      return i;
    }
  }
  return -1;
}

In this code, linearSearch
function takes an array and a value x
to search for. It iterates through the array, comparing each element with the value x
. If it finds a match, it returns the index of the element, otherwise, it returns -1.

Best-case time complexity: If the element we are searching for is present at the first index of the array, the function will return in constant time, so the best-case time complexity is O(1).
Average-case time complexity: If the element we are searching for is present somewhere in the middle of the array, the function will take approximately n/2 iterations on average to find the element. Therefore, the average-case time complexity is O(n).
Worst-case time complexity: If the element we are searching for is not present in the array, the function will have to search through the entire array, making n comparisons. Therefore, the worst-case time complexity is O(n).

Previous Lesson Next Lesson