\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt


Review Background

Idea: sample representative subproblem.

Intuition: “fences” like selection algorithm.

sampling theorem:

Recursive algorithm without boruvka: \[ T(m,n) = T(m/2,n)+O(m) + T(2n,n) = O(m+n\log n) \] (being sloppy claiming expectation on T(2n,n))

Recursive algorithm with 3 boruvka steps: $$ \begin{align*} T(m,n) &= T(m/2,n/8) + c_1( m+n) + T(n/4,n/8)\\ &\le c(m/2+n/8) + c_1 (m+n) + c(n/4+n/8)\\ &=(c/2+c_1)m + (c/8+c_1+c/4+c/8)n\\ &= (c/2+c_1)(m+n) \end{align*} $$ so set $c=2c_1$ (not sloppy: expectation works thanks to linearity).

Can show holds with high probability.