# Review 002

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