0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.