\:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}.
\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí
\:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}.
\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí