1

Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex).

It is said that adjacency list holds all the vertex in an array, and maintains a linked list of adjacent vertex, if we are to add a vertex then we need to copy the entire array to new array with extra space so the operation would take O(|v|) time but they say O(1) how is that possible ?

  • I figured I'd rather ask before editing: vertex is a singular noun. Vertices or vertexes is the plural form. It seems like you wanted the plural form (or is the singular intended)? – wvxvw Sep 20 '15 at 15:21
3

It's possible because the "lists" in an adjacency list representation are not necessarily raw arrays.

In particular, adding a new node to a linked list is an O(1) operation, so if you make the adjacency list out of linked lists then adding a new node or edge is O(1).

As the chart you've linked points out, stacks and hash tables also have O(1) insertion so you could use them as well, but stacks would probably make many other operations highly inconvenient, and hash tables are only O(1) given some strong assumptions about the hashing function that are tricky to justify, so I usually assume adjacency lists are made out of linked lists if they want constant-time node/edge insertion.

It's also worth noting that even if you did use arrays, you would still have amortized constant-time complexity for node insertion, because the worst case of O(|v|) should be a rare occurrence. It's unclear whether the chart you linked is including any amortized complexities.

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.