Some problems have a floor: no algorithm can do better than a proven bound. Knowing the floor tells you when to stop optimizing.
About 2 min of reading
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Match a cost to a known floor.
Largest of three.
Before you run it, say out loud what it will print. Then open the answer.
Binary search for 7.
Before you run it, say out loud what it will print. Then open the answer.
Set membership.
Before you run it, say out loud what it will print. Then open the answer.
Minimum of three.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
A lower bound says no algorithm in that model can do better. It is a statement about the problem, not your code.
Floors are proved inside a model, such as compares only. A different tool like a hash can step outside it.
a = [5, 9, 1]
best = a[0]
for x in a:
if x > best:
best = x
print(best)The largest item can be anywhere, so every item must be looked at. n is the floor.
a = [1, 4, 7, 9]
target = 7
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
break
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(a[mid])Order lets you throw away half each step. That reaches the log n floor for sorted data.
print(3, 4, 5)Sorting by comparing pairs cannot beat n log n. Three items need at least three compares.
a = [4, 2, 7]
s = set(a)
print(7 in s)A set lookup is not a comparison sort. The floor applies to the model, not every tool.
a = [2, 0, 1]
print(sorted(a))Sorting small integers by buckets costs linear. The n log n floor is about compares, not all sorting.
n = 1000
print(n, n * n)If the floor is n and your code costs n squared, there is a real gap. If both are n, stop tuning.
a = [3, 1, 2]
print(min(a))Finding the minimum of n items needs n minus 1 compares at least. A linear cost here is already optimal.
n = 100
print(n, n)When your cost and the floor are the same class, the algorithm is optimal. Further gains are constants.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.