# Complexities of Graph Operations

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

We'll cover the following

## 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.

Remove Vertex O(V+E) O(V2)
Remove Edge O(E) O(1)

• 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) time, because in the worst case, all the edges could be at a single vertex and, hence, we would have to traverse all E edges to reach the last one.

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

• 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) since we need to add rows and columns. We will also need to fill all the new cells.

## Comparison #

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.

In the next lesson, we will look at a special type of graph called the bipartite graph.

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