X-Nico

Expected linear time MST algorithm

Thus if the expected number of edges in a problem at the top of a left path is k then the sum of the expected number of edges in each subproblem in the left path is at most $\backslash sum\; \{d=0\}^\{\backslash infty\}\; \backslash frac\{k\}\{2^d\}=2k$ (see Geometric series).

see also