0
$\begingroup$

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

Link:- https://www.geeksforgeeks.org/graph-and-its-representations/

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Pål GD May 14 '20 at 11:59
1
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ amortized complexity* $\endgroup$ – Pål GD May 14 '20 at 11:59
0
$\begingroup$

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]

To add this graph you need to loop for each vertex and add an edge (a link) to V-1 using LinkedList

You will find that the time complexity V * (V-1) which it's O(V2)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.