0 votes 0 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? a) O(1) b) O(n) c) θ(n) d) θ(1) Programming in C asymptotic-notation data-structures + – pradeepchaudhary asked Aug 19, 2018 pradeepchaudhary 785 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply MiNiPanda commented Aug 19, 2018 reply Follow Share It should be C. O(n) means the time complexity for the given function is not more than c*n time where c is a constant. But adding node at the end of list needs the whole list to be traversed and there is no upper or lower bound to it. It is exactly equal to c*n. So Theta(n). 1 votes 1 votes Rishav Kumar Singh commented Aug 19, 2018 reply Follow Share 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. 1 votes 1 votes MiNiPanda commented Aug 19, 2018 reply Follow Share Answer would be 4 3 is theta(n) .. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Theta(n) would be more correct one as average and worst case both are covered here Kaluti answered Aug 20, 2018 Kaluti comment Share Follow See all 0 reply Please log in or register to add a comment.