Where do the log factors in Dijkstra's O((V + E) log V) binary-heap bound come from?

## Count operations, then price them The cost of Dijkstra is entirely determined by what it does to the priority queue, so the derivation is a two-line inventory. **Extractions.** Each vertex is settled exactly once, so extract-min runs V times. In a binary min-heap, extract-min moves the last element to the root and sifts it down through a tree of height `log V`, so each extraction is O(log V). Total: **O(V log V)**. **Relaxations.** Each directed edge `(u, v)` is examined exactly once - when its tail `u` is settled. If the test `dist[u] + w < dist[v]` succeeds, `v`'s key in the queue must drop, which is a decrease-key (sift up) or an insert, again O(log V). Every edge triggers at most one such update. Total: **O(E log V)**. Sum: **O((V + E) log V)**. Because a connected graph has E >= V - 1, the edge term dominates and the bound is commonly written **O(E log V)**. Note also that `log E <= log(V^2) = 2 log V`, so it makes no asymptotic difference whether the heap holds up to V entries or up to E entries - both are O(log V) per operation. ## What the logarithm is, and is not The log is the **height of the heap**, a data-structure property. It is not the depth of the graph, not the number of hops in the longest shortest path, and not related to how branchy the map is. Run Dijkstra on a straight chain of intersections and the log is still there, because the heap still has to reorder itself. ## The variants worth naming | Priority queue | Extract-min | Decrease-key | Total | |---|---|---|---| | Unsorted array, scan for min | O(V) | O(1) | O(V^2 + E) = O(V^2) | | Binary min-heap | O(log V) | O(log V) | O((V + E) log V) | | Fibonacci heap | O(log V) amortized | O(1) amortized | O(E + V log V) | The array row is not a curiosity. On a **dense** graph, where E is on the order of V^2, the heap version is O(V^2 log V) while the array version is O(V^2) - the simpler structure wins outright, and it wins on constants too. Sparse road networks, where each intersection has a handful of roads and E is roughly a small multiple of V, are the case the heap is built for: O(V log V) instead of O(V^2) is the difference between seconds and hours at a million intersections. The Fibonacci-heap row is the standard "do you know the theory" follow-up. Its bound is genuinely better asymptotically, and it is genuinely slower than a binary heap on almost every real input, because its constant factors and pointer chasing dominate at realistic sizes. This is the general shape of the trap: an asymptotic improvement promises nothing at any particular n, and here the crossover is well past the sizes anyone runs. ## Two claims to keep straight **"It's O(V log V)"** drops the edges. That would only be right if each vertex were relaxed a constant number of times, which is false - a vertex with a hundred incoming roads can have its key lowered many times. **"It's O(E log E)"** is a legitimate way to count a lazy implementation that pushes a new heap entry per successful relaxation rather than updating in place: the heap grows to O(E) entries and each operation is O(log E). Since log E and log V differ by at most a factor of two, this collapses to the same bound; say so rather than treating it as a different result. ## Where the non-heap work goes Initializing distances and building the adjacency structure is O(V + E) - linear, and swallowed by the log terms. Recovering a route from predecessor pointers is O(path length), also swallowed. There is no hidden sort of the edges anywhere; a candidate who mentions sorting edges by weight has confused the algorithm with a spanning-structure method. ## Space O(V) for distances, predecessors and the settled marks, plus the queue - O(V) with decrease-key, up to O(E) with lazy insertion. Adjacency storage is O(V + E). On a continental road graph with hundreds of millions of edges, that queue distinction stops being academic and turns into a memory-ceiling conversation.