Time Complexity / Graph Theory

Question

For my homework, I was asked a question about a given set of n nodes and m edges, where the graph was represented by an adjacency list, why insertVertex accepts O (1), and deleteVertex will accept O (m).

I'm not quite sure about my answer, but I assume that insertVertex is O (1), because when you first insert, all you add to the array is one node and a set of adjacent vertices (which means the vertices that your new node points to). Thus, this time complexity is constant. However, when you delete a node, you need to remove not only the node and adjacent edges included in the node bundle, you will also have to go through the remaining edges of m to make sure that you delete the ones that point to the node you are trying to delete (since you cannot have an edge that points to nothing.

I am new to graph theory, so I don’t know if my way of thinking is correct. Some tips would be great.

thanks

Answer 1

The explanation of O (m) is correct.

Your explanation would be better if you explained the actions in terms of related list manipulations. It takes O (1) time to add a node to the linked list. And to remove an item, O (n) time is required.

a) Why is insertVertex O (1)?

Inserting a vertex is simply adding a node to the linked list (O (1)) or 2 if the graph is not directed.

b) Why is deleteVertex O (m)?

Removing a vertex means:

1) Delete the linked list (O (1))

2) In the worst case, you will have to remove the vertex from all linked lists: O (m). This O (m) leads to the fact that the number of nodes in all linked lists is m or 2 * m if the graph is not directional.

Answer 2

insertVertex takes O (1) because you add only a new element at the end of your data structure.

deleteVertex accepts O (m), because for each edge you have to check if the edge points or points (if G is directed) from the vertex.

It looks like you have an idea reading your OP.