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