4

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?

4

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.

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.