Two parameters, one bound, no order

$O(E \log V)$ and $O(V^2)$. Which is smaller?

The question has no answer, and that is not a quibble about constants. On a graph of two thousand vertices with average degree six, the first is about sixty-six thousand and the second is four million. On a graph of two thousand vertices at half density, the first is about eleven million and the second is still four million. The two bounds cross, they cross somewhere that depends entirely on the graph, and nothing in either expression says where.

This is the ordinary situation in graph algorithms and it is almost never stated. A textbook table gives Dijkstra as $O(E \log V)$ and the array-queue version as $O(V^2)$, and a reader takes away that the first is better. It is better on some graphs.

What a sweep can and cannot separate #

The fitting machinery this site runs on takes measured counts, divides them by a candidate class, and grants the class if the ratio stays flat across the range. With one size parameter that procedure discriminates well: count ÷ n and count ÷ n log n behave visibly differently as $n$ moves over three orders of magnitude.

With two parameters it can fail silently, and the failure is worth understanding because it is a property of the experiment rather than of the algorithm.

Sweep $V$ with the average degree held fixed. Then $E = 3V$ throughout, so:

• $V$, $E$ and $V + E$ are the same curve, differing by a constant.
• $V^2$ and $VE$ are the same curve.
• $E \log V$ and $V \log V$ are the same curve.

Breadth-first search on that sweep fits $V$, $E$ and $V + E$ at a spread of 1.00 apiece. All three “fit”. None of them is evidence, because the experiment cannot tell them apart.

Now sweep $V$ at fixed density. Then $E \approx \tfrac{1}{2}dV^2$, and a different set of pairs collapses:

• $E$, $V + E$ and $V^2$ become the same curve.
• $V$ separates cleanly from all of them.

Breadth-first search on that sweep fits $V + E$ at 1.03 and $V$ alone at 9.50. Now the claim has content, and the content came from the second experiment rather than from the first.

So the honest procedure needs both sweeps, and the site’s two-variable fit takes an extra argument for exactly this: a claim is granted only when the sweep can also be shown to distinguish it from a named alternative. A fit that cannot fail is not a test, and on a single-regime sweep half of these fits cannot fail.

The full table, which is the argument #

Here is every candidate class against every algorithm, on the sparse sweep. The number is the spread of work ÷ class across $V$ from 64 to 2,048; 1.00 is a perfect fit and the tolerance is 1.6.

Every column comes in pairs. That is the sparse regime’s signature and it means the sparse regime, alone, cannot distinguish a bound in $V$ from a bound in $E$ — which is precisely the distinction the whole notation exists to make.

The same table on the dense sweep, $V$ from 64 to 512 at density 0.5:

Different pairs collapse. $E$, $V+E$ and $V^2$ are now indistinguishable, and $V$ has separated from everything.

Put the two tables together and every class is separable from every other by one sweep or the other. Neither sweep alone is enough, and this is the reason both are run.

The withdrawn claim #

Dijkstra with a binary heap declared $O(E \log V)$ in all three regimes, because that is what the bound is. On sparse graphs the fit grants it at a spread of 1.21 and on the grid at 1.36. On dense graphs it is refused at 1.82, and what fits instead is $V + E$ at 1.11.

The reason is not subtle once the work is broken apart. At $V = 512$ and half density, Dijkstra with a heap performs:

The queue — the only part the $\log V$ describes — is 2.7% of the work. Everything else is proportional to $E$, and $E$ at fixed density is proportional to $V^2$, so the total is proportional to $E$ and the logarithm never shows up.

The bound is not wrong. $E \log V$ is a correct upper bound on the queue work and therefore on the whole, and an upper bound that overstates is still a true statement. What it is not, on this family of graphs, is a description. Somebody choosing a queue on its authority is choosing on the strength of a term that is two percent of the cost.

Why the heap wins anyway, and why the folklore says otherwise #

There is a widely repeated piece of advice that follows from the crossing: use a simple array queue on dense graphs, because $V^2$ beats $E \log V$ when $E$ is near $V^2$.

Measured here, the array queue never wins. At $V = 512$ and half density the heap costs 204,687 units and the array queue costs 330,440 — the heap is ahead by a factor of 1.61. On sparse graphs it is ahead by a factor of 37.

The advice is not nonsense; it is about a different cost model, and identifying which is more instructive than either agreeing or disagreeing with it. The $V^2$ analysis assumes the graph is an adjacency matrix, so scanning a vertex’s neighbours costs $V$ rather than its degree, and the scanning term is $V^2$ for both queues. Under that model the queue is the only difference and the array wins on a dense graph. Under the model here — adjacency lists, scanning charged per edge that exists — the scanning term is $2E$ for both queues, it dominates both, and the heap’s smaller queue is a free improvement.

So the answer to “which queue on a dense graph” depends on the representation, which is a third thing the bound does not mention. What survives is the shape of the claim rather than its conclusion: the heap’s advantage collapses from thirty-seven-fold to negligible as the graph fills up, and an implementation choosing on the sparse-graph number is choosing on a number that does not apply.

The grid, where a third thing goes wrong #

Two regimes are enough to make the point about fitting. A third family makes a point about the graph that neither of the others can.

A square grid has $V$ vertices, about $2V$ edges, and — unlike a random sparse graph — a diameter of $\sqrt{V}$ rather than $\log V$. It is planar, every vertex has degree four, and it is much closer to the shape of a road network, a mesh or an image than either of the other two families.

On the grid, Dijkstra with a lazily-filled array queue does not fit $V^2$. The spread is 8.24 and the flattest candidate is $V^{3/2}$ at 1.45.

The reason is the frontier. An array queue costs one comparison per element it holds, per pop, and this implementation only holds vertices that have been reached. On a random graph the reached-but-not-settled set is a constant fraction of $V$, so $V$ pops of a $V$-sized queue give $V^2$. On a grid the frontier is a ring of about $\sqrt V$ vertices, so $V$ pops of a $\sqrt V$-sized queue give $V^{3/2}$.

The bound quoted for this algorithm is $\Theta(V^2)$ and it is correct — for the version that puts every vertex in the queue at the start with distance infinity, which is how the algorithm is usually written and is a line of code no discussion of it ever mentions. Both versions are implemented here. On the grid, the eager one costs 2,157,702 units and the lazy one costs 112,926: a factor of nineteen, from one initialisation loop, in an algorithm whose complexity is regarded as settled.

The two sweeps the regimes are read from #

The regime plate is a summary of two sweeps, and the sweeps are worth having on the page because what they show is which distinctions each regime erases.

The third narrows differently again: three algorithms rather than two or four, on the regime where the two parameters of the bound stop being independent.

What the field does about it #

Three procedural consequences, all of them small and all of them load-bearing.

Every graph claim names its regime. The declaration in the algorithm table is not a class, it is a map from regime to class, and the same algorithm carries different entries under different regimes and no entry at all where the fit refused one. Four algorithms in this field have a missing entry somewhere.

Every figure prints the regime and the range. A miss count without a line size is not a measurement, and by exactly the same argument a graph bound without a density is not a claim. The caption strip carries both.

The fit is asked to discriminate. Granting a class on a sweep where an alternative fits equally well is recorded as no evidence at all, and the assertion that enforces this has a name and rejects a real case: it refuses to accept $V + E$ from the sparse sweep alone, because on that sweep $V$ alone fits identically.

None of that is deep. It is the same discipline the sorting field already had — name the input, name the range, let the claim be refused — with one more thing to name. What is new is how much it catches: adding one parameter took four declared classes off the table, and every one of them is a class that appears in textbooks without a qualifier.

Two is not the maximum #

Graphs have two size parameters and that is already enough to break the ordering of the candidate classes. Nothing stops at two, and the problems with more are not obscure ones.

String matching has a pattern length $m$ and a text length $n$. Naive matching is $O(mn)$, Knuth–Morris–Pratt is $O(m + n)$, and Boyer–Moore is $O(n/m)$ in the good case — which is sublinear in the text, and which no ordering of the three expressions captures without knowing the ratio.

Sparse matrix multiplication has rows, columns and non-zeros, and the standard bounds mention all three. Which of $O(n \cdot \mathrm{nnz})$ and $O(\mathrm{nnz}^{1.5})$ is smaller depends on how the non-zeros are distributed, not merely on how many there are.

A hash table has a capacity $m$ and an occupancy $k$, and every interesting bound is in the ratio rather than in either. That case is instructive because the field has solved the problem by convention: everybody writes the load factor $\alpha = k/m$ and quotes bounds in it, so the two parameters were collapsed into one derived quantity by agreement, once, a long time ago.

Graph algorithms have no such convention. There is no agreed name for $E/V$, no standard practice of quoting bounds in it, and no convention that a stated bound comes with a stated regime — even though “average degree” is exactly the derived quantity that would do for graphs what the load factor does for hash tables.

Writing the bounds that way is illuminating. At average degree $d$, so $E = dV/2$:

Now they are all in one variable and they are ordered, for a fixed $d$. The first is linear, the second linearithmic, the last two quadratic — and the density has moved out of the class and into the constant, which is where a parameter that does not grow with the problem belongs.

That is the honest reading of the whole field. A density regime is a decision to treat one of the two parameters as a constant. Once it is made, everything the one-variable machinery does works again: the classes are ordered, the fit discriminates, and the constant carries the density. Refusing to make it is what leaves two bounds incomparable, and the refusal is usually not a decision at all but an omission.

What the density convention would not fix #

The load-factor analogy is illuminating and it is not sufficient, and this essay’s own tables are what show it.

A hash table’s bounds really are functions of $\alpha = k/m$. Two tables with the same load factor behave the same way whatever their sizes, which is what makes the collapse honest: the two parameters genuinely enter only through their ratio, so naming the ratio loses nothing.

Graph bounds are not functions of $d = 2E/V$, and the grid is the counterexample sitting three sections above. A random sparse graph at average degree six and a square grid at average degree four have nearly the same density — both have $E$ proportional to $V$, both are at the sparse end, and a bound quoted in $V$ and $d$ would give them the same expression. The lazily-queued Dijkstra fits $V^2$ on one and $V^{3/2}$ on the other.

So the second parameter was not the last one. What separates the two families is the size of the search frontier, which is a consequence of the diameter: a random sparse graph has diameter about $\log V$ and a reached-but-unsettled set that is a constant fraction of the graph, while a grid has diameter $\sqrt V$ and a frontier that is a ring of about $\sqrt V$ vertices. The $V^{3/2}$ is $V$ pops of a $\sqrt V$-sized queue, and the $\sqrt V$ is the diameter showing up in a cost.

That is a third parameter, it is not a size, and it is not derivable from the first two. It is also not new to this collection: the number of passes Bellman–Ford takes is exactly the source’s hop-eccentricity, and the measured pass counts are the diameters of the three families rather than anything about $V$ or $E$.

Two families of graphs at the same density, and two different classes for the same code. A convention that named only the density would make those two rows look comparable and they are not.

Which does not make the convention worthless #

The right conclusion is narrower than abandoning the idea, and it is worth stating because the same move is available in every field with more than one parameter.

A derived ratio is a legitimate collapse exactly when the cost is genuinely a function of it. For hash tables that is true and the collapse is total. For graphs the density collapses the $V$-against-$E$ ambiguity — which is the ambiguity this essay opened with, and which is real — and leaves the shape ambiguity untouched. That is still most of the way, because $V$ against $E$ is where the incomparable bounds are and the shape effect shows up in one algorithm of five.

So the practice the field should adopt is not one number but a stated regime, which is what this collection’s plates already carry: the family, the density and the range. Three graphs of the same density from three families are three experiments, and every table above is printed per family for exactly that reason.

And the general form is the useful thing to take away, because it applies wherever a bound has more parameters than a reader can hold. Ask which parameters the cost is actually a function of, then quote the bound in those and treat everything else as a regime to be named. For sorting it is one and the convention is invisible. For hash tables it is one derived from two, agreed long ago. For graphs it is at least three, no convention exists, and the tables in this essay are what a field looks like before it has one.

The general form #

The trouble here is not really about graphs. It is the missing argument again, with a second axis, and the second axis makes it much harder to ignore.

With one parameter, an unstated input distribution can make a bound misleading by a factor. Insertion sort is $\Theta(n)$ or $\Theta(n^2)$ depending on the input, and both are true statements about the same code. That is bad enough, and at least the two classes are ordered: whichever input arrives, the quadratic case is worse than the linear one.

With two parameters, the classes are not ordered, so the missing argument does not merely change how bad the answer is. It changes which answer is better. Two implementers can each measure carefully, each get a correct result, and reach opposite conclusions about the same pair of algorithms — because they measured different graphs and neither wrote the density down.