Lower Bound
noun
say it: “LOH-er BOWND” /ˈloʊɚ baʊnd/
A floor on how little work a kind of problem can take: no method of that kind can do better.
What is a lower bound?
A lower bound is a floor: the least work any method of a certain kind must do. Sorting by comparing items has a lower bound of about n log n comparisons in the worst case, so no comparison sort can beat it, however clever. Textbooks write lower bounds with Ω, read "big omega".
In a sentence
- “Sorting by comparing has a lower bound of about n log n comparisons in the worst case.”
Level: Freelancer · More Software Development terms at this level
Updated