Noesis
3.1.6 · D5Complexity Analysis

Question bank — Tight bounds — Θ notation; lower bounds — Ω notation

1,424 words6 min read↑ Back to topic

True or false — justify

Every algorithm is also .
True — the in Big- is a ceiling, and a higher ceiling is never violated; eventually, so any bound implies a bound.
Every algorithm is also .
False — a ceiling that low can be broken; itself is but exceeds every for large , so no statement holds.
is symmetric: .
True — a two-sided sandwich pins both curves to the same shape, so swapping roles just swaps the two constants for their reciprocals.
is symmetric, so follows.
False — Big- is a one-way ""; holds but does not. Only is symmetric.
If then also and .
True — is defined as the conjunction of both bounds; the sandwich literally contains a ceiling and a floor.
Big- describes an algorithm's best case.
False — describe how a chosen function grows; best/worst/average is a separate axis (which input). You can put on the worst-case function itself.
An algorithm can be in the worst case and in the best case at once.
True — these are statements about two different functions (worst-case cost and best-case cost); no contradiction because they describe different inputs.
Insertion sort's overall runtime is .
False — best case is , worst is ; since orders differ, no single covers the whole runtime — only and .
.
True — a constant function is trapped between two constant multiples of (e.g. ), so its growth shape is "flat," i.e. .
.
True — logs of different bases differ only by the constant factor , and constant factors are exactly what ignores.
.
True — , a constant factor of , which swallows; so the two are the same growth shape.
.
False — , so their ratio is not a bounded constant; dominates and no floor stays below .
If then must eventually exceed .
False — it must exceed some where may be tiny (e.g. ); the floor is a scaled copy, not itself.

Spot the error

"Merge sort is , therefore it is ." — what's missing?
An statement alone gives only a ceiling; needs a matching floor too. It happens to hold here, but by itself never establishes it.
"Since , we have ." — what's wrong?
That inequality is a floor (an direction), not a ceiling. For you must bound the expression above, e.g. .
" but not , so has no tight bound." — fix it.
It has no tight bound relative to , but is perfectly tight against the right reference. "No " only means no single-order runtime, not "no against anything."
"Because , the two are interchangeable." — why is the notation abused?
The "=" in asymptotics is a one-way "is a member of the class," not equality. Writing reverses the only legal direction .
", so ." — where's the slip?
means is strictly smaller order (): it's but not , so the floor fails and there is no .
"Worst case is , so the algorithm is ." — what's conflated?
A on the worst-case function is not a on the whole runtime; the best case may be a lower order, leaving the overall runtime without a single .
"To prove I found one input where is large." — why insufficient?
requires the floor to hold for all , not a single lucky point; growth statements are about eventual, sustained behavior.

Why questions

Why does the constant appear in every definition?
To ignore constant factors — a machine twice as slow shouldn't change an algorithm's growth class, so absorbs that scaling.
Why does the threshold appear?
To ignore small- noise like startup costs or a slow first pass; only the eventual trend as defines the class.
Why is Big- alone considered "loose"?
It only promises a ceiling; a fast algorithm can sit far below it (every is trivially ), so need not describe the true growth.
Why do we need in addition to ?
To assert a floor — that the cost can't sneak below a shape — which combined with the ceiling pins the growth exactly.
Why does a lower bound on a problem (not an algorithm) matter?
It certifies that no algorithm whatsoever can beat it; e.g. for comparison sorting means cleverness can't break the barrier, so any matching algorithm is optimal.
Why does the limit test give when ?
A finite nonzero ratio is a bounded constant factor between the curves, which is precisely the sandwich that defines .
Why is the only symmetric one of the three?
Because it's a two-sided trap; swapping and just flips the sandwich around, whereas one-sided and each pick a single direction.

Edge cases

Is a constant-time function or ?
— you cannot use as a reference because the sandwich requires ; the reference for "flat growth" is the constant .
Can ever be a valid reference in these definitions?
No — the definitions require with a positive floor, so a zero reference collapses the sandwich and is disallowed.
Does the limit test still decide the class when does not exist?
Not directly — an oscillating ratio may stay bounded between two positive constants (still ) or not; you must fall back to the sandwich definition with explicit .
Is closer to or ?
Neither — grows strictly faster than and strictly slower than , so it is of neither; it sits in its own class .
For very small can legally exceed the ceiling?
Yes — the ceiling only binds for , so any finite number of early violations is permitted and ignored.
Does require and to ever be equal?
No — it only requires scaled by two constants to trap ; the curves may never touch, they just grow at the same rate.
If best and worst case have the same order, does a single exist?
Yes — when best and worst collapse to one order (e.g. merge sort, always ), the whole runtime shares that single tight bound.
Recall The two traps that catch everyone

Trap 1 — bound vs case: bound a function; best/worst/average pick which function. They are perpendicular axes. Trap 2 — loose vs tight: is only a ceiling and only a floor; you never earn until both are proven with the same shape.

Connections