X-Nico

Expected linear time MST algorithm

The expected number of F-light edges in G is at most n/p where n is the number of vertices in G

•

The root has m edges so the expected number of edges is equal to 2m plus twice the expected number of edges in each right subproblem.

•

If a parent problem has x edges then the expected number of edges in the left child problem is at most x/2.

•

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