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.

• 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. Commented Feb 11, 2022 at 7:17
• @Russel can't the same idea be applied to an adjacency matrix, which is listed as O(V^2) Commented Feb 11, 2022 at 7:21
• Are you referring to the resizing of the array? Yes you can. Commented Feb 11, 2022 at 7:25
• So in that case is the average time complexity of adding a vertex to an adjacency matrix O(1) as well? Commented Feb 11, 2022 at 7:28
• @terrabyte You will struggle with that one. You need to copy a lot of information over. Commented Feb 11, 2022 at 7:52

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.