Characterizing running times

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

1. 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.
2. Drop detail only after bounding. Constants and lower-order terms vanish asymptotically, but justify the step with constants, thresholds, or known growth rules.
3. 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.
4. 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)). $$

5. 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.
6. 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.