2 つの表現の計算量

$G=(V,E)$ を頂点数 $n=|V|$、辺数 $m=|E|$ のグラフとする。

(a) 隣接行列表現は $\Theta(n^2)$ 語の記憶領域を使う。与えられた $u,v$ について辺の有無の判定は $O(1)$ 時間、$u$ に隣接するすべての頂点の列挙は $\Theta(n)$ 時間、すべての辺の走査は $\Theta(n^2)$ 時間で行える（かつ、それより速くはできない）。

(b) 隣接リスト表現は $\Theta(n+m)$ 語の記憶領域を使う。$u$ に隣接するすべての頂点の列挙は $\Theta(1+\deg u)$ 時間、すべての辺の走査は $\Theta(n+m)$ 時間で行える。一方、与えられた $u,v$ について辺の有無の判定は、最悪 $\Theta(\deg u)$ 時間かかる。