big Omega notation
A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.
In more detail
Where Big O caps the cost from above, Omega guarantees a floor. The best case of linear search is Omega(1), because finding the target in the first slot costs one comparison. The lower bound for comparison sorting, Omega(n log n), says that no comparison-based sort can do better in the worst case.
Related terms
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- big Theta notation — A way of writing an exact growth rate: Theta(f(n)) means the cost is both O(f(n)) and Omega(f(n)).
- comparison sort lower bound — The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers