Member-only story
Source:- Time complexity of Quick Sort
For more questions and answers visit our website at Frontend Interview Questions
Quick sort is a popular sorting algorithm that uses the divide-and-conquer approach to sort a list of elements. The algorithm works by selecting a pivot element from the list, partitioning the remaining elements into two sub-lists based on whether they are less than or greater than the pivot, and recursively applying the same process to each sub-list. The algorithm terminates when the sub-lists are of size zero or one, which are by definition sorted.
The time complexity of Quick sort depends on the choice of pivot element and the order of the input data. In the best case, where the pivot divides the list into two equal sub-lists, the time complexity of Quick sort is O(n log n), where n is the number of elements in the list. In the worst case, where the pivot is repeatedly chosen as the smallest or largest element, the time complexity of Quick sort can degrade to O(n²). However, the average time complexity of Quick sort is O(n log n), making it one of the most efficient sorting algorithms.