Inserting vertex in an adjacency matrix

Question

If a graph with $v$ vertices is represented in the form of adjacency matrix .

Then, adding a new vertex to the existing graph requires how much time ?

Is it $O(v^2)$ or $O(2v)$ .

We have the adjacency matrix of the graph with $v$ vertices , by adding a new vertex we have to enter a row (for edges leaving the new vertex) and a column(for incident edges of new vertex) and an entry for self loop . So ,there is a need to update $2v+1$ new entries. So i am in favor of $O(2v)$. Did i miss something ? Is there any need for creating new empty matrix of size $(v+1)^2$ and then copying $v^2$ existing elements and updating remaining $2v+1$ entries of new vertex , which takes $O(v^2)$ time.

Thanks in advance .

Answer 1

This is completely implementation-dependent. As you say, if you need to copy the existing matrix, you have $n^2$ entries to copy, which takes $\Theta(n^2)$ steps; if you only need to add the new entries (for example, if you've pre-allocated a large matrix but you're adding the vertices one at a time), you only need to write $O(n)$ entries each time.

If you did have to copy the matrix every time you grow it, a more time-efficient option would be to start with a small matrix (say, $10\times 10$) and double it every time it fills up. Doing it that way means you need fewer expensive copies but the potential down-side is that you could waste a lot of space. For example, if your graph ends up having 21 vertices, you'll have allocated a $40\times 40$ matrix, most of which is empty. You could mitigate that by not growing the array so aggressively (say, making it 25% bigger each time it grows, instead of 100%).