Complexities of Graph Operations

Time complexities

Below you can find the time complexities for the four basic graph functions.

In this table, V means the total number of vertices, and E means the total number of edges in the graph.

Operation	Adjacency List	Adjacency Matrix
Add Vertex	$O(1)$	$O(V^2)$
Remove Vertex	$O(V+E)$	$O(V^2)$
Add Edge	$O(1)$	$O(1)$
Remove Edge	$O(E)$	$O(1)$

Adjacency list

• Addition operations in adjacency lists take constant time as you only need to insert at the head node of the corresponding vertex.

• Removing an edge takes $O(E)$ time because in the worst case, all the edges could be at a single vertex; hence, you would have to traverse all E edges to reach the last one.

• Removing a vertex takes $O(V + E)$ time because you have to delete all its edges and then reindex the rest of the list one step back to fill the deleted spot.

Adjacency matrix

• Edge operations are performed in constant time as you only need to manipulate the value in the particular cell.

• Vertex operations are performed in $O(V^2)$ since you need to add rows and columns. You will also need to fill all the new cells.

Comparison

Both representations are suitable for different situations. If your model frequently manipulates vertices, then the adjacency list is a better choice.

If you are dealing primarily with edges, the adjacency matrix is the more efficient approach.

---

Keep these complexities in mind because they will give you a better idea about the time complexities of the several algorithms that you will see in this section.