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?
why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?
algorithms;math;complexity;graph;big o
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 an O(|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.