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)). $$

1. 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.
2. 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: