In website geeksforgeeks i read that adding a vertex to graph in adjacent matrix takes O(V^2) time but i am not getting it. It requires adding a row and a column which should take linear time ? I am a beginner hence forgive me for such a question

• Try to implement it yourself and see how you (a) get O(1) query and (b) what you need to do to extend the graph. When you add a column you actually have to replace the entire row. – Pål GD May 14 '20 at 11:59

It more or less depends on the implementation. If you have implemented the matrix using linked lists (which isn't what we usually do), then adding a new vertex in $$G$$ will be linear in the number of vertices of $$G$$. But we don't usually use linked lists because then reading/checking an edge will take $$V(G)^2$$ time.

To allow random/constant time access of the adjacency matrix, we need to use fixed-size arrays of arrays (or matrix). Now, when you add new vertex, we are required to copy the whole matrix into a bigger size matrix: hence the quadratic time.

Generally, we use $$vectors$$ instead of $$arrays$$ which hold extra hidden memory, and hence it will indeed be linear time to add a vertex on average. https://www.geeksforgeeks.org/vector-in-cpp-stl/

• amortized complexity* – Pål GD May 14 '20 at 11:59

Yes will takes O(V2), Suppose you have a small graph from vertices 1, 2, 3, 4 and each vertex connected to each other, So you have

1 [2, 3, 4]
2 [1, 3, 4]
3 [1, 2, 4]
4 [1, 2, 3]