Algorytm Borůvki: Różnice pomiędzy wersjami

Łatwo udowodnić, że każdym kolejnym wywołaniu liczba wierzchołków zmaleje co najmniej dwukrotnie - zatem wywołań tych będzie co najwyżej <math>log(n)</math>. Złożoność obliczeniowa całości zależy więc od sposobu implementacji kroków 1,2 algorytmu. Zastosowanie w implementacji struktur [[Union-find]] pozwala osiągnąć złożoność na poziomie <math>O(log(n)*m)</math>. Można zmodyfikować go tak, aby osiągnąć złożoność <math>O(log(n)*m - n)</math> - algorytm działa wtedy znacznie szybciej dla grafów rzadkich; dla grafów gęstych modyfikacja nie daje dużych zysków czasowych.