educative.io

Educative

Time complexities of adjacency matrix

One of our readers sent us the following feedback:

The time complexities of the adjacency matrix in the table should be O(V^2).

Hi,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your feedback, the time complexities mentioned in the table are for the edges. Each cell of the adjacency matrix represents one edge. This cell can be referenced using two indices. This indexing of the 2D will only take constant time, i.e, O(1). However, the complexity of the vertex operations can be O(V^2), especially in the case of adding a vertex or removing one. This would call for reinitialization of the 2D array and copying all elements from the previous matrix to the new one. I hope this clears things up.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

2 Likes

Adding the same explanation to the course would really help.