Complexities of Graph Operations

Let's discuss the performance of the two graph representation approaches.

Time Complexities

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

Note that 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(1) O(V2)O(V^2)
Remove Vertex O(V+E)O(V+E) O(V2)O(V^2)
Add Edge O(1)O(1) O(1)O(1)
Remove Edge O(E)O(E) O(1)O(1)

Adjacency List

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

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

  • Removing a vertex takes O(V+E)O(V + E) time because we have to delete all its edges and then re-index the rest of the array one step back in order to fill the deleted spot.

Adjacency Matrix

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

  • Vertex operations are performed in O(V2)O(V^2) since we need to add ​rows and columns. We will also need to fill all the new cells.


Both representations are suitable for different situations. If your model frequently manipulates vertices, 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 we’ll see in this section.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.