Skip to main content

Time Complexity for Searching and Sorting Algorithms

Time Complexity for Searching and Sorting Algorithms


Every algorithm works with its own complexity level and Time complexity of an algorithm tells us the time consumed to execute n number of inputs on a system . Many of the algorithms work better with small number of inputs but can not perform better with large number of inputs .

There are 3 different cases for complexity as below -

1. Best Case Time Complexity -

The best time in which we can obtain desired output from an algorithm shows best case for that algorithm and shown by Omega ( Ω ) Notation . We also say this  Lower Bound because it is the minimum possible time to get desired outpit with that algorithm .

2. Worst Case Time Complexity -

The Worst time in which we obtain desired output from an algorithm shows Worst case for that algorithm and shown by Big Oh( O ) Notation .  We also say this  Upper Bound because it is the maximum possible time to get desired outpit with that algorithm .

3. Average Case Time Complexity -

The Average time in which we obtain desired output from an algorithm shows Average case for that algorithm and shown by Theta( θ ) Notation .  We also say this  Mid Bound because it is the Average possible time to get desired outpit with that algorithm .

Time Complexity for various Searching and Sorting Algorithms -

Algorithms Best Case or
Lower Bound or
Ω Notation 
Average Case or
Mid Bound or
θ Notation
Worst Case or
Upper Bound or
Big oh Notation
Linear Search Ω(1) θ(n) O(n)
Binary Search Ω(1) θ(log n) O(log n)
Bubble Sort Ω(n) θ(n^2) O(n^2)
Selection Sort Ω(n^2) θ(n^2) O(n^2)
Insertion Sort Ω(n) θ(n^2) O(n^2)
Merge Sort Ω(n log n) θ(n log n) O(n log n)
Quick Sort Ω(n log n) θ(n log n) O(n^2)
Bucket Sort Ω(n+k) θ(n+k) O(n^2)
RadixSort Ω(nk) θ(nk) O(nk)