liveBook · Manning

Lower bound

As explained in Algorithms Every Programmer Should Know

A lower bound is a limit that a quantity does not asymptotically fall below.

A lower bound is a limit that a quantity does not asymptotically fall below. In algorithm analysis, it can describe a best-case bound; Big Omega notation expresses it. section 1.3

For linear search, finding the target first takes the fewest steps; finding it last is the worst case. A* search also uses a lower bound: an admissible heuristic estimates the remaining cost without ever overestimating it. section 1.3 section 12.1

Table 12.1 Common admissible heuristics
Problem Domain
Heuristic h(n)
Why it never overestimates
Road network routing
Euclidean Distance (Straight Line)
A road can only be longer than a straight line between two points, never shorter
Grid-based movement (4 directions)
Manhattan Distance
No sequence of horizontal/vertical moves can cover the required displacement in fewer steps
Grid-based movement (8 directions, diagonals allowed)
Chebyshev Distance
A diagonal move covers one unit of both axes at once, so this is the true minimum move count on an open grid.
Sliding-tile puzzle
Sum of each tile Manhattan distance from its goal position
Every tile must travel at least that many rows and columns, even if no tile were in the way.

Compare admissible lower-bound heuristics for road routes, grids, and sliding-tile puzzles. section 12.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains best- and worst-case linear search and shows how admissible heuristics lower-bound remaining path cost.
Examples
Uses the first and last positions in linear search, plus Manhattan distance for grids and tile puzzles.
What you can do after
Evaluate algorithm behavior by comparing best and worst cases, and recognize heuristics that never overestimate path cost.
How it connects
Connects lower bounds to algorithm analysis, Big Omega notation, Big O notation, A* search, and admissible heuristics.

Also explained in

Compare how 2 books explain lower bound →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.