0 0 votes Time taken in adding/removing an edge to/from adjacent list ? Algorithms algorithms graph-algorithms + – vaishali jhalani 1.0k views answer comment Share Follow Print See all 6 Comments 6 6 Comments reply Prashant. commented Nov 5, 2016 reply Follow flag O(n). time when All elemets related to one edge. 0 0 replyShare Digvijaysingh Gautam commented Nov 5, 2016 reply Follow flag 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 0 0 replyShare saurabh rai commented Nov 5, 2016 reply Follow flag 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. 0 0 replyShare vaishali jhalani commented Nov 5, 2016 reply Follow flag Is somewhere time is related to degree of a particular vertex ? 0 0 replyShare Prashant. commented Nov 5, 2016 reply Follow flag yes saurabh if u add in starting then yes take constant time. 0 0 replyShare santhoshdevulapally commented Nov 6, 2016 reply Follow flag 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) 0 0 replyShare Please log in or register to add a comment.
