그래프 G = (V, E)를 표현하는 데 인접 행렬을 사용한 경우와 인접 리스트를 사용한 경우에 필요한 공간을 비교하는 것은 간단하다. |V|가 그래프의 정점 수라고 하면 인접 행렬은 |V|² 원소를 갖게 되고, 마찬가지로 |E|가 그래프의 간선 수고 무방향 간선을 두 번 계산한다면 인접 리스트의 표현은 |V| 크기의 배열과 |E|만큼의 간선을 포함하는 |V| 리스트들을 가질 것이다. 그래서 인접 리스트 표현은 |V| + |E|만큼의 아이템을 요구할 것이고, 이는 그래프가 밀집되지 않고 정점이 각각에 연결되지 않았다면 |V|²보다 훨씬 작은 값일 것이다.

이렇게 되면 굳이 인접 행렬을 고민할 필요가 없다고 생각할 수도 있다. 그러나 생각해 볼 2가지가 있다. 첫째는 인접 행렬이 더 간단하다는 것이다. 행렬 이외의 다른 것을 알 필요가 없다. 둘째로 인접 행렬이 더 빠르다. 행렬의 원소에 접근하는 것은 상수 시간이 걸리는 연산으로 모든 간선 또는 원소를 다른 무엇보다 빨리 탐색할 수 있다. 이는 행렬의 왼쪽 위에 있든 오른쪽 아래에 있든 상관없다. 인접 리스트를 사용하면 그림 2-18의 왼쪽에 있는 정점들의 배열에서 오른쪽에 있는 원소에 접근해야 하고, 정점에서 출발하는 리스트를 탐색하여 원하는 간선을 찾아야 한다. 그래서 노드 4와 5가 연결되었는지 알려면 먼저 정점 행렬에서 노드 4로 가야 하고, 그다음 2와 3, 마지막으로 5까지 건너가야 한다. 노드 4와 0이 연결되었는지를 보려면 4에서 시작하는 모든 리스트를 탐색하여 끝까지 가야 하고, 결국 0을 찾을 수 없다는 사실을 발견한 후에야 링크로 연결되지 않았다는 것을 알게 된다. 혹자는 0에서 출발하는 리스트가 더 짧으니 0에서 출발하여 탐색한다면 더 빠를 수도 있다고 반론할 수도 있지만, 그것을 알 방법은 없다.

빅오 표기법으로 한 정점이 다른 정점에 연결되었는지를 판단하는 데는 상수 시간이 걸리므로 인접 행렬을 사용하면 복잡도는 Θ(1)이 된다. 같은 연산에 인접 리스트를 사용하면 O(|V|) 시간이 걸린다. 이는 그래프에서 하나의 정점이 다른 모든 정점에 연결될 수 있고, 하나의 이웃을 찾기 위해 인접 리스트 전체를 탐색해야 할 수도 있기 때문이다. 알다시피, 공짜는 없다. 컴퓨터에서는 속도를 위해 공간을 희생하는 절충안이 있다. 이와 같은 절충안을 종종 사용하는데, 공간-시간 절충(space-time tradeoff)이란 용어로 부른다.