Search and Sort Algorithm Big O Notation

Linear Search

• Best Case: O(1) — The target element is the first element.

• Average Case: O(n) — The target element is somewhere in the middle or not in the array.

• Worst Case: O(n) — The target element is the last element or not present.

Binary Search

• Best Case: O(1) — The target element is the middle element.

• Average Case: O(log ⁡n) — The target element is not immediately found but within the sorted array.

• Worst Case: O(log⁡ n) — The target element is at the extreme ends or not present.

Interpolation Search

• Best Case: O(1) — The target element is exactly where the interpolation suggests.

• Average Case: O(log ⁡log⁡ n) — Uniformly distributed data.

• Worst Case: O(n) — Highly skewed data distribution or worst interpolation.

Depth-First Search (DFS)

• Best Case: O(1) — The target node is found immediately.

• Average Case: O(V+E)— Typically when all nodes and edges must be explored.

• Worst Case: O(V+E) — The target node is the last one discovered.

Breadth-First Search (BFS)

• Best Case: O(1) — The target node is the root or the first node checked.

• Average Case: O(V+E) — All nodes and edges need to be explored.

• Worst Case: O(V+E) — The target node is the last one explored.

Bubble Sort

• Best Case: O(n) — The array is already sorted (with an optimized version that stops early).

• Average Case: O(n²) — Average case with random elements.

• Worst Case: O(n²) — The array is sorted in reverse order.

Selection Sort

• Best Case: O(n²) — Selection sort does not improve with better input, always O(n²).

• Average Case: O(n²) — Average case with random elements.

• Worst Case: O(n²) — Selection sort is insensitive to input order.

Insertion Sort

• Best Case: O(n) — The array is already sorted.

• Average Case: O(n²) — Average case with random elements.

• Worst Case: O(n²) — The array is sorted in reverse order.

Merge Sort

• Best Case: O(n log⁡ n) — time complexity is the same in all cases.

• Average Case: O(n log⁡ n).

• Worst Case: O(n log⁡ n).

Quicksort

• Best Case: O(n log⁡ n) — The pivot splits the array into two nearly equal halves.

• Average Case: O(n log⁡ n) — Average case with random pivots.

• Worst Case: O(n²) — The pivot is always the smallest or largest element, leading to unbalanced partitions.

Heap Sort

• Best Case: O(n log⁡ n) — time complexity is the same in all cases.

• Average Case: O(n log⁡ n).

• Worst Case: O(n log⁡ n).

Counting Sort

• Best Case: O(n+k)— k is the range of the input.

• Average Case: O(n+k).

• Worst Case: O(n+k).

Radix Sort

• Best Case: O(n*k) — k is the number of digits in the largest number.

• Average Case: O(n*k).

• Worst Case: O(n*k).

Bucket Sort

• Best Case: O(n+k) — k is the number of buckets; assumes uniform distribution.

• Average Case: O(n+k).

• Worst Case: O(n²) — All elements end up in one bucket (degenerate case).

Shell Sort

• Best Case: O(n log n) — Occurs when the array is already sorted or nearly sorted, especially when using a good gap sequence like the Knuth sequence.

• Average Case: O(n^(3/2)) or O(n^1.5) — Highly dependent on the gap sequence used. With commonly used sequences like the Knuth sequence, the average-case complexity is approximately O(n^1.5).

• Worst Case: O(n²) — Can degrade to O(n²), particularly with poorly chosen gap sequences like the original Shell sequence (where the gaps are halved each time).