クラスカル法
グラフ内の辺数を E、頂点数を V とすると、クラスカル法の計算量はデータ構造が単純であれば O(E log E) または O(E log V) である。これらは次の理由で等価である。
E は最大でも V であり、log V = 2 log V であるから log E は O(log V) である。
孤立した頂点はそれ自体が必ず最小全域木となるので無視すると、V ≤ E+1 であるから log V は O(log E) である。
この計算量は以下のように求められる。まず、辺を重みでソートするのに比較ソートを用いると O(E log E) となる。これにより、「S から重みが最小の辺を削除する」操作を定数時間で行えるようになる。次にどの頂点がどの木に属しているかを保持するのに素集合データ構造を使う。各辺について、2回の探索操作と1回の和集合操作が必要であり、O(E) 回となる。単純な素集合データ構造であっても O(E log V) の時間内に O(E) 回の操作を実行できる。したがって、総計算量は O(E log E) = O(E log V) である。
辺が事前にソート済みか(分布数えソートや基数ソートを使って)線形時間でソートできる場合、より洗練された素集合データ構造を使うことができ、O(E α(V)) の計算量になる。ここでαはアッカーマン関数の逆関数で極めてゆっくり増加する。