The Gateway to Computer Science Excellence
0 votes
Time taken in adding/removing an edge to/from adjacent list ?
in Algorithms by Active (4.8k points) | 94 views
O(n). time when All elemets related to one edge.
In case of adjacency list we have to travel the linked list so it takes O(n) and in case of adjacency matrix it it takes O(1) becoz we just have to put 0 in the cell of corresponding matrix
I think to remove an edge will take O(n) nd adding an edge will take constant time.
where n is no of edges in graph originally.
Is somewhere time is related to degree of a particular vertex ?
yes saurabh if u add in starting then yes take constant time.

we can insert new node at start node or last node.

if we insert at first node only one pointer variable is changed so time complexity is o(1),but at last we can traverse the linked list so time complexity is o(n).

in case of deletion we exactly dont know where the required node present so time complexity is o(n)

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,919 users