Pr\{X \geq a\} \leq E[X] / a

\sum_{i = 1}^n i = n(n+1)/2

H_n = \sum_{i = 1}^n 1/i \leq \ln(n+1) \in O(\log n)

W(n) \in O(k \cdot f(n)) \geq 1 - \left(\frac{1}{n}\right)^k

Dijkstra's Algorithm: O(m + n \log n)

A* Algorithm: h(u) \leq \delta(u, v) + h(v), h(v) \leq \delta(v, t) (optional), h(t) = 0

Bellman-Ford: O(mn\log n) work, O(n \log n) span with table, O(mn) work and O(n \log n) span with sequence

BFS: O(d\log n) span and O(m+n) work

DFS: tree-based O((m+n)\log n), array sequence and adjacency sequences O(m+n)

```
SCC (G = (V, E)) = let
F = decreasingFinish G
G^T = transpose G
SCCOne ((X, comps), v) = let
(X', comp) = DFSReach G^T (X, v)
in
(X', comp::comps) (* here: you can check for empty comp if you want *)
end
in
iterate SCCOne ({}, []) F
end
```

The overall number of comparison is

\begin{align*}
E[W] =& \sum_{i < j} \frac{2}{j - i + 1}\\
=& 2\sum_{i = 0}^{n - 1} \sum_{j = i+1}^{n - 1} \frac{1}{j - i + 1}\\
=& 2\sum_{i = 0}^{n - 1} \sum_{k = 1}^{n - i - 1} \frac{1}{k + 1} \tag{let $k = j - 1$}\\
=& 2\sum_{i = 0}^{n - 1} (H_{n - i} - 1)\\
\leq& 2\sum_{i = 0}^{n - 1} (1 + \log(n - i) - 1)\\
=& 2\sum_{i = 0}^{n - 1} \log(n - i)\\
\in& O(n \log n)\\
\end{align*}

Table of Content