iii. Complexity, Constraints and Amortized Analysis

Read the constraints, compute the real operation count, and that number tells you the intended solution.

Asymptotic notation

Notation	Meaning	Reads as
$f=O(g)$	$\exists c,n_0:f(n)\le c\cdot g(n)$ for $n\ge n_0$	$f$ grows no faster than $g$ (upper bound)
$f=\Omega (g)$	$\exists c,n_0:f(n)\ge c\cdot g(n)$ for $n\ge n_0$	$f$ grows no slower than $g$ (lower bound)
$f=\Theta (g)$	$f=O(g)$ and $f=\Omega (g)$	$f$ and $g$ grow at the same rate
$f=o(g)$	$f(n)/g(n)\to 0$	$f$ is strictly smaller order than $g$
$f=\omega (g)$	$f(n)/g(n)\to \infty$	$f$ is strictly larger order than $g$

In competitive programming "$O(g)$" is almost always used loosely to mean $\Theta (g)$ (a tight bound, not just an upper one) — stating a true-but-weak bound like “bubble sort is $O(n^{100})$” is correct but useless, so the convention is to always give the tightest bound you can prove. $o$ and $\omega$ matter mainly for lower-bound arguments (e.g. “no comparison sort can be $o(n\log n)$”).

Which guarantee do you actually have, since they give different promises for the same stated bound:

Guarantee	Promise	Example
Worst case	true for every input of size $n$	quicksort is $O(n^2)$ worst case
Average case	true in expectation over a fixed distribution of inputs (usually uniform random)	quicksort is $O(n\log n)$ on random input
Expected (randomized algorithm)	true in expectation over the algorithm’s own random choices, for every input	randomized quicksort is $O(n\log n)$ expected, on any input
Amortized	true for the total cost of $n$ operations, divided by $n$ — individual operations may be expensive	vector::push_back is $O(1)$ amortized, $O(n)$ worst case for one call

Only worst case is safe against an adversary who sees your algorithm (adaptive interaction, anti-hash tests, a judge with hacked tests); average case needs the input to actually be drawn from the assumed distribution (an adversarial judge input breaks it, which is exactly why plain quicksort on adversarial data degrades to $O(n^2)$ and randomized pivoting fixes it); expected and amortized both hold unconditionally over all inputs, but expected is a per-call promise (randomized over the algorithm) while amortized is a total-cost promise (divided evenly, no randomness required).

What fits in one second

About $10^8$-$10^9$ simple operations per second: $10^9$ for vectorisable array loops, $10^8$ for cache-missing or branchy code, $10^7$ for map, modulo-heavy or long double code.

$n$	Target	Typical tools
$\le 10$-$11$	$O(n!\cdot n)$	permutations, brute force
$\le 18$-$22$	$O(2^{n}n)$, $O(2^n{n}^2)$	bitmask DP, SOS
$\le 16$	$O(3^n)$	submask enumeration
$\le 40$	$O(2^{n/2})$	meet in the middle
$\le 100$	$O(n^4)$	interval DP with extra dimension
$\le 500$	$O(n^3)$	Floyd, Hungarian, interval DP
$\le 5000$	$O(n^2)$	quadratic DP, $O(V^2)$ Dijkstra
$\le 10^5$	$O(n\sqrt{n})$, $O(n{\log }^{2}n)$	Mo, sqrt decomposition, CDQ, HLD
$\le 10^6$	$O(n\log n)$	sorting, segment tree, FFT
$\le 10^7$-$10^8$	$O(n)$, $O(n\log \log n)$	linear sieve, prefix sums, two pointers
$\le 10^{12}$	$O(\sqrt{n})$	trial division, harmonic lemma
$\le 10^{11}$	$O(n^{2/3})$, $O(n^{3/4}/\log n)$	Du’s sieve, Min-25, Lucy
$\le 10^{18}$	$O(\log n)$, $O({\log }^{2}n)$	binary exponentiation, digit DP, matrix power

Other constraint clues:

• $\sum n\le 2\cdot 10^5$ across tests: per-test cost must depend on that test’s $n$, never on MAXN.
• $q$ and $n$ both $10^5$ with “online” or forced decoding (x ^= lastAns): you need a persistent or online structure, not Mo or offline sorting.
• An oddly small parameter (alphabet $\le 20$, $k\le 10$, values $\le 100$, at most 3 special vertices) is the exponential or DP dimension.
• A time limit of 5+ s with $n=10^5$ suggests $O(n\sqrt{n}\log n)$ or a bitset $O(n^2/64)$.
• Memory limits below 64 MB rule out $O(n\log n)$ persistent structures on $10^6$.

Memory

Type	Elements in 256 MB
char / bool	$2.6\cdot 10^8$
int	$6.7\cdot 10^7$
long long / double	$3.3\cdot 10^7$
bits in a bitset	$2.1\cdot 10^9$

• vector overhead is 24 bytes, so vector<vector<int>> with $10^6$ rows costs 24 MB plus heap headers before any data.
• set/map nodes cost about 40-48 bytes plus the key.
• A persistent segment tree with $q=2\cdot 10^5$ updates on $n=2\cdot 10^5$ needs about $q(\log n+1)+2n\approx 4.4\cdot 10^6$ nodes. At 12 bytes each that’s 53 MB.
• Recursion: each frame is roughly 50-200 bytes.

Useful magnitudes

Quantity	Value
$2^{10},2^{20},2^{30},2^{60}$	$\approx 10^3,10^6,10^9,10^{18}$
double exact integers	up to $2^{53}\approx 9\cdot 10^{15}$
$20!$	$2.4\cdot 10^{18}$ (fits in ll); $21!$ does not
$\left(\genfrac{}{}{0ex}{}{60}{30}\right)$, $\left(\genfrac{}{}{0ex}{}{66}{33}\right)$	$1.2\cdot 10^{17}$, $7.2\cdot 10^{18}$
$\pi (10^6)$, $\pi (10^7)$, $\pi (10^9)$	78498, 664579, 50847534
max divisors of $n\le 10^6$ / $10^9$ / $10^{18}$	240 / 1344 / 103680
max distinct prime factors, $n\le 10^{18}$	15
prime gap below $10^{18}$	under 1500
partitions $p(100)$	$1.9\cdot 10^8$
Catalan $C_{19}$, $C_{35}$	$1.8\cdot 10^9$, $3.1\cdot 10^{18}$
Bell $B_{15}$	$1.4\cdot 10^9$
$H_n\approx \ln n+0.5772$	$H_{10^6}\approx 14.39$
${\sum }_{p\le n}1/p\approx \ln \ln n+0.2615$	sieve work is $O(n\log \log n)$
$\alpha (n)$	at most 4 for any practical $n$

Asymptotics in practice

• With several parameters, keep them all: $O(n+m)$, $O(nm/w)$, $O(|\Sigma |n)$.
• Common sums: ${\sum }_{i\le n}n/i=\Theta (n\log n)$, ${\sum }_{d\mid n}1=O(n^{1/3})$ in practice, ${\sum }_{i\le n}\lfloor n/i\rfloor$ has $O(\sqrt{n})$ distinct values, a loop where j *= 2 gives $\log$.
• ${\log }_2(n!)=\Theta (n\log n)$, so comparison sorting is $\Omega (n\log n)$. Any algorithm that could sort by comparisons inherits the bound (for example element distinctness, convex hull via the lift to a parabola).
• Expected, amortized and worst case are different promises. All three are fine for a total time limit; only worst case is safe against adaptive interaction or persistence.

Recurrences

Recurrence	Solution	Where
$T(n)=T(n/2)+O(1)$	$O(\log n)$	binary search
$T(n)=T(n/2)+O(n)$	$O(n)$	quickselect, median of medians
$T(n)=2T(n/2)+O(n)$	$O(n\log n)$	merge sort, D&C
$T(n)=2T(n/2)+O(n\log n)$	$O(n{\log }^{2}n)$	CDQ with a sort or BIT
$T(n)=3T(n/2)+O(n)$	$O(n^{1.585})$	Karatsuba
$T(n)=7T(n/2)+O(n^2)$	$O(n^{2.807})$	Strassen
$T(n)=T(n/5)+T(7n/10)+O(n)$	$O(n)$	median of medians
$T(n)=2T(n-1)+O(1)$	$O(2^n)$	Hanoi
$T(n)=T(\sqrt{n})+O(1)$	$O(\log \log n)$	van Emde Boas
$T(n)=2T(n/2)+O(n/\log n)$	$O(n\log \log n)$	outside the master theorem

Master theorem for $T(n)=aT(n/b)+f(n)$: compare $f(n)$ with $n^{{\log }_{b}a}$. If $f$ is polynomially smaller, the leaves dominate and $T=\Theta (n^{{\log }_{b}a})$. If they are equal up to ${\log }^k$, $T=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$. If $f$ is polynomially larger (and regular), $T=\Theta (f)$.

Proof: the three cases, via the recursion tree

Unrolling $T(n)=aT(n/b)+f(n)$ gives a tree of depth $L={\log }_{b}n$: level $i$ has $a^i$ nodes, each on a subproblem of size $n/b^i$, contributing $a^{i}f(n/b^i)$ of non-recursive work; the leaves (level $L$) number $a^L=n^{{\log }_{b}a}=n^{c^{\ast }}$ (writing $c^{\ast }={\log }_{b}a$) and contribute $\Theta (1)$ each, i.e. $\Theta (n^{c^{\ast }})$ total. So $T(n)=\Theta (n^{c^{\ast }})+{\sum }_{i=0}^{L-1}{a}^{i}f(n/b^i)$. Write the level sum, for $f(n)=\Theta (n^c)$, as $a^i(n/b^i{)}^c=n^c\cdot (a/b^c{)}^i$ — a geometric series in $i$ with ratio $r=a/b^c$, and $r>1⟺c<c^{\ast }$, $r=1⟺c=c^{\ast }$, $r<1⟺c>c^{\ast }$ (since ${\log }_{b}a=c^{\ast }$). Case 1 ($c<c^{\ast }$, $r>1$): the series grows with $i$, so it is dominated by its last term $i=L-1$, which is $\Theta (n^c\cdot r^L)=\Theta (n^c\cdot n^{c^{\ast }-c})=\Theta (n^{c^{\ast }})$ — matching the leaf cost, giving $T(n)=\Theta (n^{c^{\ast }})$. Case 3 ($c>c^{\ast }$, $r<1$, with the regularity condition $af(n/b)\le \kappa f(n)$ for some $\kappa <1$ ensuring the recursive work doesn’t blow up): the series shrinks with $i$, dominated by its first term $i=0$, namely $f(n)$ itself, and the leaf term $\Theta (n^{c^{\ast }})$ is asymptotically smaller since $c>c^{\ast }$ — giving $T(n)=\Theta (f(n))$. Case 2 ($f(n)=\Theta (n^{c^{\ast }}{\log }^{k}n)$, $r=1$): each level sum is $a^i(n/b^i{)}^{c^{\ast }}{\log }^k(n/b^i)=n^{c^{\ast }}{\log }^k(n/b^i)$ exactly (the $r^i$ factor is $1$), and summing ${\log }^k(n/b^i)=\Theta ((L-i{)}^k)$ over $i=0,\dots ,L$ gives $\Theta (L^{k+1})=\Theta ({\log }^{k+1}n)$ (a standard power-sum bound), so $T(n)=\Theta (n^{c^{\ast }}{\log }^{k+1}n)$. The sharper case $T(n)=aT(n/b)+c{n}^d$ is checked by brute-force simulation (counting operations against the closed form) in Divide and Conquer. $■$

Akra-Bazzi for uneven splits: find $p$ with $\sum a_i{b}_i^p=1$; then $T(n)=\Theta (n^p(1+{\int }_1^{n}g(u)/u^{p+1}du))$. Example: $T(n)=T(n/3)+T(2n/3)+n$ gives $p=1$ and $\Theta (n\log n)$.

Recursion tree intuition: if level costs shrink geometrically the root dominates, if they’re equal multiply by the depth, if they grow the leaves dominate.

A linear recurrence $a_n=c_1{a}_{n-1}+\cdots +c_k{a}_{n-k}$ has a closed form via the characteristic polynomial’s roots; compute the $n$-th term in $O(k^3\log n)$ with matrix power or $O(k\log k\log n)$ with Bostan–Mori (Linear Recurrences).

Amortized analysis

The total cost of a sequence is bounded even if single operations are expensive.

• Aggregate. Bound the total directly. A monotonic stack pushes each element once and pops it at most once, so a while loop that sometimes pops $n$ items is still $O(n)$ overall.
• Accounting. Overcharge cheap operations and save the credit. push_back with doubling: charge 3 per insert, and each element pays for its own future copy and one copy of an older element.
• Potential. Pick $\Phi \ge 0$ with ${\Phi }_0=0$. The amortized cost is $c_i+{\Phi }_i-{\Phi }_{i-1}$, and the sum telescopes. Binary counter: $\Phi$ = number of ones, so an increment flipping $k$ ones has amortized cost $(k+1)+(1-k)=2$.

The workhorse arguments:

Argument	Used by
each element is pushed and popped once	monotonic stack/queue, two pointers, two-stack queue
a pointer never decreases more than it increases	prefix function, Z-function, Kasai’s LCP, Ukkonen
the smaller side moves, so each element moves $O(\log n)$ times	small-to-large, union by size, DSU on tree, HLD light edges
each merge destroys a distinct value or a node	segment tree beats ($\Phi$ = number of distinct values), segment tree merging ($\Phi$ = number of nodes), Chtholly tree with random assigns
$\Phi =\sum \log (\text{subtree size})$	splay trees, link-cut trees: $O(\log n)$ amortized

To prove a new bound: find what makes an operation expensive, find a non-negative quantity that the expensive step decreases, and bound how much cheap steps increase it.

When amortization breaks

• Rollback undoes the progress that paid for the work. Rollback DSU must use union by size without path compression ($O(\log n)$ worst case).
• Persistence lets an expensive old version be reused many times. Splay trees and doubling vectors lose their bounds.
• Adversarial interaction with a per-query time limit can hit the worst case of every operation.

Complexity trade-offs in practice

Big-O hides constants that decide accepted vs TLE. Rough throughput on a judge (simple operations per second): additions in a tight loop $\sim 10^9$; random memory accesses $\sim 10^8$; map/set operations $\sim 10^7$; hash map operations $\sim 3\cdot 10^7$.

Choice	Prefer when
$O(n\sqrt{n})$ (Mo, sqrt decomposition) vs $O(n{\log }^{2}n)$	$n\le 2\cdot 10^5$: both fine; sqrt has better constants with simple arrays
segment tree vs Fenwick	Fenwick when the operation is invertible: 2–3$\times$ faster, less code
set vs sorted vector	static data: sorted vector + lower_bound (cache-friendly)
online vs offline	offline lets you sort queries, use CDQ, or reverse time
recursion vs iteration	depth $>10^5$: iterate (stack limit)
exact long double vs integer	integers whenever possible (exact and faster)
$O(n\log n)$ sort vs counting sort	values up to $10^6$: counting / radix

Choosing block sizes

For a sqrt decomposition with update cost $O(B)$ and query cost $O(n/B)$, the balanced choice is $B=\sqrt{n}$; if updates are $u$ times more expensive per element than queries, take $B=\sqrt{n/u}$. For Mo’s algorithm with $q$ queries, $B=n/\sqrt{q}$ minimizes $O(qB+n^2/B)$.

Proof: optimal block size

The total cost $f(B)=aB+\frac{bn}{B}$ is convex in $B>0$ with $f^{\prime }(B)=a-\frac{bn}{B^2}$, which vanishes at $B=\sqrt{bn/a}$, giving $f=2\sqrt{abn}$. For Mo, the right pointer moves $O(n)$ per block ($n/B$ blocks, $n^2/B$ in total) and the left pointer $O(B)$ per query ($qB$), so $B=n/\sqrt{q}$ and the total is $O(n\sqrt{q})$.

Profiling

Generate a max test (and adversarial ones: sorted, all equal, star graph, long path), run with time, and look at which loop dominates before optimizing anything.

Related: Complexity and Analysis, Sqrt Decomposition, Mo’s Algorithm.