Programming
๐ Searching Algorithm Complexity ๐
Best, average, and worst case complexity for linear search, binary search, hashing, and balanced-tree based search โ quick revision notes with when to use each.
Algorithms
Searching
Big O
Complexity
Study Notes
โ Previous
๐ข Algorithmic Complexity: Big O From First Principles
Next โ
โก Sorting Algorithm Complexity ๐
๐ Searching Algorithm Complexity
| # | Algorithm | โฑ๏ธ Best | โ๏ธ Average | ๐ป Worst | ๐พ Space | โ๏ธ Stability |
|---|---|---|---|---|---|---|
| 1๏ธโฃ | ๐ถโโ๏ธ Linear Search | O(1) | O(n) | O(n) | O(1) | โ Yes |
| 2๏ธโฃ | ๐ฏ Binary Search | O(1) | O(log n) | O(log n) | O(1) | โ Yes |
| 3๏ธโฃ | ๐ช Jump Search | O(1) | O(โn) | O(โn) | O(1) | โ Yes |
| 4๏ธโฃ | ๐งฉ Interpolation Search | O(1) | O(log log n) | O(n) | O(1) | โ Yes |
| 5๏ธโฃ | โก Exponential Search | O(1) | O(log n) | O(log n) | O(1) | โ Yes |
| 6๏ธโฃ | ๐งฎ Fibonacci Search | O(1) | O(log n) | O(log n) | O(1) | โ Yes |
| 7๏ธโฃ | ๐ข Hashing Search | O(1) | O(1) | O(n) | O(n) | โ Yes |
| 8๏ธโฃ | ๐ณ Binary Search Tree (BST) | O(1) | O(log n) | O(n) | O(n) | โ Yes |
| 9๏ธโฃ | ๐ฒ Balanced BST (AVL, Red-Black) | O(1) | O(log n) | O(log n) | O(n) | โ Yes |
Notes
- Binary Search requires sorted data.
- Hashing gives average constant-time lookup but degrades to O(n) on collisions.
- Balanced Trees ensure logarithmic performance by maintaining structure.
- Jump and Interpolation searches are useful for uniformly distributed data.
Related Posts
- ๐งฑ Data Structures & Big O Complexity โ the underlying structures (arrays, BSTs, hash tables) these search algorithms run against
- โก Sorting Algorithm Complexity โ Binary Search's sorted-data prerequisite is what a sorting algorithm provides
