Fix complexity of Dijkstra's algorithm

jakobkogler · web-flow · commit 0804f4111892 · 2018-04-09T10:43:21.000+02:00
Error mentioned here: e9d37eb#r28480357
diff --git a/src/graph/dijkstra_sparse.md b/src/graph/dijkstra_sparse.md
@@ -9,7 +9,7 @@ We recall in the derivation of the complexity of Dijkstra's algorithm we used tw
 the time of finding the unmarked vertex with the smallest distance $d[v]$, and the time of the relaxation, i.e. the time of changing the values $d[\text{to}]$.
 
 In the simplest implementation these operations require $O(n)$ and $O(1)$ time.
-Therefore, since we perform the first operation $O(n)$ times, and the second one $O(m)$ times, we obtained the complexity $O(n^2 m)$.
+Therefore, since we perform the first operation $O(n)$ times, and the second one $O(m)$ times, we obtained the complexity $O(n^2 + m)$.
 
 It is clear, that this complexity is optimal for a dense graph, i.e. when $m \approx n^2$.
 However in sparse graphs, when $m$ is much smaller than the maximal number of edges $n^2$, the complexity gets less optimal because of the first term.
