Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex).
But I couldn't find a reason why? Since all we need is to add a row and a column, which of course takes O(|v|), what is the reasoning behind this?
Best Answer
Matrixes are typically stored in contiguous memory, and the content must have a defined mapping from the sequential memory layout to matrix cell
(x,y)(a typical mapping is described in this former "Programmers" post). Now, if there is to add a new vertex, one has to increase the storage for a|V|²matrix to(|V|+1)². That means you will have to copy the whole content of the former smaller matrix to the newly allocated memory for the bigger matrix, because the mapping won't fit anymore. And that is obviously anO(|V|²)operation.One can mitigate this problem by providing a better memory allocation strategy, for example, by not increasing the matrix size one-by-one, but in bigger steps.