For a randomized routing algorithm, how does expected-case complexity differ from average-case?

### The three quantifiers Every complexity claim hides a quantifier, and "averaged over what?" is the question that exposes it. For an algorithm A and inputs of size n: - **Worst case** — the maximum cost over all inputs. No randomness, no assumptions: `max over x of cost(A, x)`. - **Average case** — the mean cost over an *assumed distribution D on inputs*: `E over x drawn from D of cost(A, x)`. The algorithm may be entirely deterministic; the randomness is a claim you are making about the data. - **Expected case** — the mean cost over the *algorithm's own random choices*, for each fixed input, usually reported as the worst such mean: `max over x of E over r of cost(A, x, r)`. The randomness belongs to the algorithm, not the data, so the bound holds for **every** input. That last point is the whole distinction. An average-case bound is a conditional promise: it holds while your inputs behave as assumed. An expected-case bound is unconditional over inputs and conditional only on your random source — you supply the randomness yourself, so nobody can take it away from you by sending unusual data. ### The routing example Suppose a request router assigns each arriving request to one of m targets by drawing uniformly at random, and you want to reason about the work per request. If you say **"average O(1)"**, you are asserting something about the request stream: given the mix of requests you expect, the mean work per request is constant. An unusual day — a burst from one tenant, a retry storm, a migration that changes the key mix — falsifies the assumption, and with it the bound. The input chose the bad case. If you say **"expected O(1)"**, you are asserting something about the router's own dice: for any request stream at all, the mean work per request over the router's random choices is constant. The bad case still exists — it is the run where the draws clump — but it is selected by your random source rather than by the traffic, and it differs from run to run on the same input. ### What expected does *not* promise An expected-time bound is a statement about the mean. It caps no individual run. An expected-O(1) operation can occasionally be far more expensive; the guarantee is that such runs are rare, not that they are absent. This is why an expected-case bound and a latency SLO are different objects: percentile targets live in the tail, and the tail is exactly what an expectation averages away. When randomized behaviour matters for latency, the useful follow-up is a **concentration** claim — not just "the mean is O(f(n))" but "the probability of exceeding c times that is smaller than some rapidly shrinking bound in n" — which is a strictly stronger statement than the expectation alone. ### Where randomization actually helps Randomization does not delete a worst case; it relocates it. Before randomization, a specific input triggers the bad behaviour deterministically, every single time, and it will keep doing so on every retry. After randomization, the bad behaviour requires an unlucky sequence of internal choices, so the same input is usually fine, a retry is an independent trial, and no property of the data can force the bad path repeatedly. "Unlikely and non-repeatable" is a much better operational position than "guaranteed whenever this shape of input arrives", which is why randomized pivots, random probe orders and random tie-breaking are worth their cost. It is worth separating two families here, because they trade different things away. A **Las Vegas** algorithm is always correct and its *running time* is the random variable — a randomized pivot choice is the classic example. A **Monte Carlo** algorithm has bounded running time and its *answer* carries a small probability of being wrong. Expected-time analysis is the natural language for the first family; probability-of-error analysis is the language for the second. ### How to state each one so it survives review A defensible bound names its quantifier. "Expected O(1) per assignment, over the router's own random draws, for any request stream" is checkable. "Average O(1)" is only checkable once you add "under a request mix with these properties", and it needs monitoring, because distributions drift while code does not. And "worst case O(m)" is checkable by construction — it assumes nothing, which is why it is the number you plan capacity against even when you expect never to see it. ### The one-line test Ask of any average: **over what?** If the answer is "over inputs", you owe the reader a distribution and a way to notice when it stops holding. If the answer is "over the algorithm's coin flips", you owe the reader nothing about the data — but you also cannot promise anything about a single run.