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