Complexity Analysis

Big-O bounds the growth of a function; the case — best, worst, average — chooses which function you bound. They are independent axes: a worst case can have O, Theta, and Omega bounds, and a best case can meaningfully be Omega(n).

Expected case averages over the algorithm's own random choices, so it holds for every input. Average case averages over an assumed input distribution and collapses if that assumption is wrong. Randomization moves the uncertainty from the data to the coin flips.

E and S are independent inputs, so neither provably dominates the other. Lower-order terms may only be dropped within a single variable. O(E+S) becomes O(E) only when the problem guarantees S is bounded by a multiple of E.

Do the arithmetic instead of labelling both 'exponential'. At n=12 there are 4,096 subsets but 479 million orderings — a gap of five orders of magnitude. Subsets stay tractable to roughly n=25-30; orderings die around n=12-14.

The master theorem covers only T(n) = a·T(n/b) + f(n), where a subproblem is n divided by a constant b above 1. Subtracting one leaves no such b, so no case applies. Summing the per-call work gives Θ(n^2).

The base case stops it. After k substitutions the expression reads 2^k·T(n/2^k) + k·cn; you stop when n/2^k hits the base-case size, at k = log2 n. That is where the accumulated cn per round becomes cn log n.

Memoization pays only when the same key is requested repeatedly. Its memory is distinct keys reached times bytes per entry, so a wide key space visited once each — every product-and-region pair in a nightly sweep — costs everything and saves nothing.

Nothing is violated: an amortized O(1) structure is allowed to let one call absorb work that many cheap calls prepaid, and that call lands in some request's p99. Fix the tail by spreading the bulk step out or moving it off the request path.

An amortized bound covers the total cost of a sequence, not any one call. The append that fills the buffer copies every element, costing Theta(n), and that single call blows a per-operation deadline no matter how good the average is.

A slice that copies costs time proportional to its length, so taking the remaining suffix on every iteration copies a quadratic total of characters — O(n^2) time and allocation. Passing start and end offsets instead keeps the pass linear.

Every iteration moves at least one index, each index moves in only one direction, and together they can cover at most n positions before meeting. So the loop runs at most n times, whatever the body does per pass.

Promise a measured percentile, not an asymptotic class. A hash lookup is expected O(1) and worst-case O(n) for a single operation, so the SLA states a p99 latency at a named key volume and load, with the distribution assumption written down.

Formally yes: for large enough n the 5n log n term dominates. But 200n is the larger term for every n below roughly 10^12, so the label predicts the growth shape, not the runtime anyone will measure.

An algorithm that skips even one packet is defeated by an adversary who plants the duplicate there, so exact detection over a raw n-packet stream is Omega(n). A sublinear claim means work moved, the guarantee weakened, or n means something smaller.

Count the distinct reachable states the cache key can take, then multiply by the work each state does outside recursion. A key holding a subset of n items has 2^n values — caching helps enormously and still leaves you exponential.

Per-level work halves as you descend: n^2, then n^2/2, then n^2/4. The series sums to under 2n^2, so the root call dominates and the total is Θ(n^2). Multiplying per-call work by depth only works when levels cost the same.

Size it as distinct keys times realistic bytes per entry, not raw key bytes: a billion 16-byte keys lands in tens of gigabytes. Above RAM, partition by key hash, order the data so duplicates meet, or accept an approximate filter.

Breadth-first peak memory is the widest level, depth-first peak memory is the height. A wide, shallow org chart has a frontier of 100,000 nodes but a depth of two or three, so the queue explodes while the recursion barely nests.

At n = 50 the quadratic pass is about 2,500 operations and the alternative about 280 — both invisible, so runtime cannot decide. Correctness risk and maintenance cost do; ship the simple version and enforce the cap.

Accept it when an enforced bound caps the input, the measured cost at ten times today's volume still fits the budget, and the simpler code is clearer. Then encode that bound as validation plus a test that fails when it is exceeded.

Probably not on performance grounds alone: at 5,000 records the quadratic step is about 2.5x10^7 element operations, typically tens of milliseconds. Decide on exposure instead — how firm the cap is, what happens when it breaks, and who maintains the harder code.

A proven lower bound is not the negotiable part, so the only lever is the problem statement: weaken exactness, shrink the input covered, or move the cost off the latency path. Pick the relaxation whose failure mode the business can absorb.

Decide by who controls the depth. If the nesting comes from outside your trust boundary it is unbounded, and the fixed stack ceiling becomes a remote crash switch — so cap the accepted depth or keep pending work off the call stack.

Every seed except the winner must lose a comparison before it can be ruled out, and one comparison rules out at most one seed. With n-1 to eliminate, no correct algorithm uses fewer than n-1 comparisons.

Little-o is strictly stronger: o(n log n) means the running time grows strictly slower than n log n — their ratio tends to zero — while O(n log n) permits growth exactly proportional to n log n. Neither promises anything about constants or small inputs.

It solves to Θ(n^(log_2 3)), about Θ(n^1.585), by case 1: the watershed beats the linear combine, so the leaves dominate. It outruns the quadratic schoolbook method only above a crossover size, because its constants, temporaries and call overhead are far larger.