Time complexity of adding a vertex to adjacency list

Question

Multiple sources state that the time complexity of adding a vertex to an adjacency list is O(1) and my understanding right now is that this is because of optimizations with hash tables.

If we use an array of linked lists, then the time complexity is O(V) right? Because to add a new vertex we have to make a new array of size V + 1.

I just wanted to confirm my line of thinking against pre-existing information.

• Russel: If you are to use an array of lists, then yes. Since, as you already noted, you will create a new, larger array and copy everything to it. But you might want the size of this array to be some factor larger, say 2 times than the current.
• terrabyte: @Russel can't the same idea be applied to an adjacency matrix, which is listed as O(V^2)
• Russel: Are you referring to the resizing of the array? Yes you can.
• terrabyte: So in that case is the average time complexity of adding a vertex to an adjacency matrix O(1) as well?
• Ainsley H.: @terrabyte You will struggle with that one. You need to copy a lot of information over.

Answer 1

In an array of list implementation of adjacency list, the worst-case cost of adding a new vertex is $O(V) $ because in the worst-case the array is full and you need to create a larger array which is say 2 times larger than the current. Then you will then copy the $V$ lists. The cost of copying a list is $O(1)$ assuming we are copying the pointer to a list and not copying each entries of the list.

However, the amortized cost of inserting is $O(1)$. Please refer to the amortized analysis of dynamic arrays (https://en.m.wikipedia.org/wiki/Amortized_analysis) .

As for the adjacency matrix, you can also dynamically resize but the worst-case cost of insert is $O(V^2)$ since we are to copy individual items. The amortized cost of insert is $O(V) $ applying the same dynamic array analysis.