Arcadi4/nerdy / clrs/characterizing-running-times
characterizing-running-times
VerifiedUse when analyzing algorithm running time, asymptotic notation, Big O, Omega, Theta, little-o, little-omega, growth-rate comparisons, loop bounds, recurrence terms, or textbook-style asymptotic exercises.
Characterizing Running Times
Overview
Use asymptotic notation to state the simplest precise growth bound for an algorithm or function. Always name the quantity being bounded: worst case, best case, all inputs, space, recurrence term, or another explicit quantity.
Shared CLRS Conventions
Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style.
When to Use
- Analyzing algorithms, loops, recurrences, or pseudocode running time.
- Comparing growth rates: logarithms, polynomials, exponentials, factorials, iterated logarithms, and Fibonacci numbers.
- Proving or checking asymptotic claims.
- Fixing sloppy statements such as saying a lower bound is "at least Big O" or claiming an unqualified running time when only the worst case is tight.
Core Workflow
- Name the case. Say "worst-case running time," "best-case running time," or "running time for all inputs." A worst-case tight bound does not imply every input has that running time.
- Drop detail only after bounding. Constants and lower-order terms vanish asymptotically, but justify the step with constants, thresholds, or known growth rules.
- Choose notation by claim strength. Use O for upper bound, Omega for lower bound, Theta for tight bound, little-o for non-tight upper bound, and little-omega for non-tight lower bound.
- For Theta, prove both sides. Use Theorem 3.1:
$$ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n)). $$
- For algorithm lower bounds, construct hard inputs. A worst-case lower bound means: for every sufficiently large input size, at least one input of that size takes that much time.
- Use the simplest precise expression. Prefer:
$$ \Theta(n^2) $$
over:
$$ \Theta(3n^2 + 20n). $$
Prefer Theta over O when the bound is tight.
Notation Reference
Assume functions are asymptotically nonnegative.
O-notation: asymptotic upper bound. There are positive constants and a threshold such that eventually:
$$ 0 \le f(n) \le c g(n). $$
Omega-notation: asymptotic lower bound. There are positive constants and a threshold such that eventually:
$$ 0 \le c g(n) \le f(n). $$
Theta-notation: tight bound. There are positive constants and a threshold such that eventually:
$$ 0 \le c_1 g(n) \le f(n) \le c_2 g(n). $$
little-o notation: non-tight upper bound. For every positive constant, eventually:
$$ 0 \le f(n) < c g(n). $$
When the limit exists, this is equivalent to:
$$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0. $$
little-omega notation: non-tight lower bound. For every positive constant, eventually:
$$ 0 \le c g(n) < f(n). $$
When the limit exists, this is equivalent to:
$$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty. $$
Do not say "at least O." Say Omega for a lower bound. Do not use O when you mean a tight bound; say Theta.
Growth-Order Ladder
For common positive functions, from slower to faster:
$$ 1 < \lg^* n < \lg\lg n < \lg n < (\lg n)^k < n^\epsilon < n < n\lg n < n^a < c^n < n! < n^n $$
where the constants satisfy:
$$ k \ge 1, \quad \epsilon > 0, \quad a > 1, \quad c > 1. $$
Key rules:
- Changing logarithm bases changes only a constant factor.
- Any positive polynomial beats any polylogarithm:
$$ (\lg n)^k = o(n^\epsilon). $$
- Any exponential with base greater than one beats any polynomial:
$$ n^b = o(a^n) \quad \text{for } a > 1. $$
- Factorials beat fixed-base exponentials but are below the self-power:
$$ n! = \omega(2^n) $$
and
$$ n! = o(n^n). $$
- Stirling's approximation gives:
$$ \lg(n!) = \Theta(n\lg n). $$
- Fibonacci numbers grow exponentially:
$$ F_i = \Theta(\phi^i), \quad \phi = \frac{1 + \sqrt{5}}{2}. $$
- Floors and ceilings usually do not change polynomial growth:
$$ \lceil n \rceil^k = \Theta(n^k) $$
and
$$ \lfloor n \rfloor^k = \Theta(n^k) $$
for constant powers when the expressions are defined appropriately.
Worked Pattern: Insertion Sort
Upper bound for all inputs:
- The outer loop runs:
$$ n - 1 $$
times.
- For outer index value:
$$ i, $$
the inner loop runs at most:
$$ i - 1 \le n - 1 $$
times.
- Total inner-loop work is at most:
$$ (n - 1)(n - 1) < n^2, $$
with constant work per iteration.
- Therefore insertion sort runs in:
$$ O(n^2) $$
time on all inputs.
Worst-case lower bound:
- Put the largest third of the values in the first third of the array.
- After sorting, those values must move to the last third.
- Each of those values crosses at least the middle third of positions one step at a time.
- That forces:
$$ \Omega\left(\frac{n}{3} \cdot \frac{n}{3}\right) = \Omega(n^2) $$
moves for such inputs.
Conclusion: insertion sort's worst-case running time is:
$$ \Theta(n^2), $$
but its best-case running time is:
$$ \Theta(n). $$
It is correct to say insertion sort runs in:
$$ O(n^2) $$
time for all inputs, but incorrect to say its running time is:
$$ \Theta(n^2) $$
without qualifying worst case.
Equations and Anonymous Functions
Asymptotic notation denotes sets, but equations conventionally use equality.
Standalone right side means set membership:
$$ 4n^2 + 100n + 500 = O(n^2). $$
Inside formulas, asymptotic notation means an unnamed function in that set:
$$ 2n^2 + 3n + 1 = 2n^2 + \Theta(n). $$
Left-side notation is coarser on the right:
$$ 2n^2 + \Theta(n) = \Theta(n^2). $$
Each occurrence of asymptotic notation is a separate anonymous function unless the expression clearly binds it, for example:
$$ \sum_{i=1}^{n} O(i). $$
Common Mistakes
- Mistake: Putting quick scratch-work expressions in prose before switching to display blocks. Fix: Move every threshold, comparison, ratio, and bound into a display block, even if it appears only in setup or explanation.
- Mistake: Starting with planning paragraphs that mention formulas before the final answer. Fix: Start directly with the final response and put all scratch work that remains visible into display blocks.
- Mistake: Putting formulas in headings or inline dollar math. Fix: Use formula-free headings and put the expression in the next display block.
- Mistake: "Worst case is Theta of n squared, so the algorithm's running time is Theta of n squared." Fix: Say "worst-case running time" unless every input has that growth.
- Mistake: "An O of n log n algorithm is faster than an O of n squared algorithm." Fix: O is only an upper bound; compare tight Theta bounds when possible.
- Mistake: "At least O of n squared." Fix: Use Omega for lower bounds.
- Mistake: Ignoring negative lower-order terms too early. Fix: Use definitions. This expression is not bounded above by a constant multiple of n squared:
$$ \frac{n^3 - 100n^2}{n^2} = n - 100. $$
- Mistake: Treating little-o like O. Fix: The first relation is true; the second is false:
$$ 2n = o(n^2), \quad 2n^2 \ne o(n^2). $$
- Mistake: Treating little-omega like Omega. Fix: This is tight, not little-omega:
$$ \frac{n^2/2}{n^2} = \frac{1}{2}. $$
- Mistake: Misordering slow functions. Fix: The iterated logarithm grows slower:
$$ \lg^* n < \lg\lg n. $$
Quick Proof Recipes
- Polynomial: An asymptotically positive degree-d polynomial is:
$$ \Theta(n^d). $$
- O proof: Bound every lower term by the highest-order term after a threshold, then choose one constant.
- Omega proof: Keep a positive fraction of the dominant term after lower-order subtractions become small enough.
- little-o or little-omega proof: Compute the limit of the ratio when possible; zero gives little-o and infinity gives little-omega.
- Loop upper bound: Bound maximum iterations per loop level and multiply or sum.
- Loop lower bound: Identify many operations that must happen for a family of inputs.
- Recurrences: Keep anonymous linear or constant terms as asymptotic blocks when exact lower-order details do not affect the asymptotic solution.
Related skills
| Skill | Stars | Updated | Works with | Status | Install |
|---|---|---|---|---|---|
| slack-gif-creatoranthropics/skillsKnowledge and utilities for creating animated GIFs optimized for Slack. Provides constraints, validation tools, and animation concepts. Use when users request animated GIFs for Slack like "make me a GIF of X doing Y for Slack." | Stars: 197k | Updated | Claude CodeCodex | Verified | Install |
| ponytailDietrichGebert/ponytailLazy senior dev mode for any coding task: the smallest change that fully solves it, and a reply a busy human understands in one read. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |
| ponytail-debtDietrichGebert/ponytailHarvest every shortcut: comment into one debt ledger, so deferrals get tracked instead of forgotten. One-shot report. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |
| ponytail-debtDietrichGebert/ponytailList every `shortcut:` comment (and older `ponytail:` ones) as a debt ledger. One-shot report, changes nothing. Use for "ponytail debt", "what did ponytail defer", "list the shortcuts", /ponytail-debt. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |