5 votes 5 votes What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? O(n) O(1) θ(n2) θ(n) DS data-structures linked-list time-complexity + – hacker16 asked Nov 14, 2017 recategorized Jul 7, 2022 by Lakshman Bhaiya hacker16 3.4k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply joshi_nitish commented Nov 14, 2017 reply Follow Share both O(n) and θ(n) are correct. 1 votes 1 votes hacker16 commented Nov 14, 2017 reply Follow Share Okay! i don't know why, but the answer key go with θ(n). But i also clearly agree with both the options. 0 votes 0 votes Harish Kumar 2 commented Nov 14, 2017 reply Follow Share I think in general it should be O(n) as best case is O(1) answorst is O(n). But the question specifies that we have to add a node at last when the pointer is initially at start. So in best case and worst case both it comes O(n) that's why the answer is Theta(n). 1 votes 1 votes chandra sai commented Nov 14, 2017 reply Follow Share in any case, you need to reach the last node to insert new node so it cant be done by traversing less than n nodes.so theta(n) is correct 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Answer would be 4- theta(n) However o(n) is also possible but most appropriate will be theta(n) because here on both worst and best case we have to traverse at the end of list to add the new node.. vamp_vaibhav answered Nov 24, 2017 vamp_vaibhav comment Share Follow See 1 comment See all 1 1 comment reply Anmol Verma commented Nov 17, 2018 reply Follow Share In both the case, as we have to ultimately traverse to the end of linked list the how it can become Theta(n)....??? 0 votes 0 votes Please log in or register to add a comment.