1 votes 1 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) Confused between option (b) and (c) . DS data-structures linked-list time-complexity + – arya_stark asked Jul 4, 2018 • retagged Jul 7, 2022 by Lakshman Bhaiya arya_stark 21.0k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply bhuv commented Jul 4, 2018 reply Follow Share Then you must read about asymptotic notations either from an online portal or from the CLRS book. The answer would be theta(n) as in question it is mentioned the pointer will be at starting node so in both worst and best case it will take O(n) that's why answer will become Theta(n). Also before posting the question search it on google and on the site, someone might be already asked that question and got the answer it will save your time too. This question is already posted before here https://gateoverflow.in/170133/linked-list-time-complexity. 0 votes 0 votes arya_stark commented Jul 4, 2018 reply Follow Share i didn't get this. bdw thnxx. 0 votes 0 votes Sanjay Sharma commented May 3, 2020 reply Follow Share number of operations are fixed here as n . which is both upper and lower bound by some k n where k can be any positive constant so O(n) as well as Ω(n) so ans is both O(n) as well as Θ(n) 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes option (c) because in the best case you will have to traverse the entire linked list and in the worst case you will have to traverse the entire linked list to reach at the last node and adding the new element in constant time so theta(n) is best option. Anil Ji answered Jul 4, 2018 • selected Nov 30, 2018 by arya_stark Anil Ji comment Share Follow See all 3 Comments See all 3 3 Comments reply arya_stark commented Jul 4, 2018 reply Follow Share Got it... Thnxx Sir!! 0 votes 0 votes bhuv commented Jul 4, 2018 reply Follow Share reach at the last node and deleting the element in constant tme so theta(n) is best option. Which element are you deleting in last? Question is about adding a node. 0 votes 0 votes Anil Ji commented Jul 4, 2018 reply Follow Share edited..deleting or adding after reaching the last node will take constant time 1 votes 1 votes Please log in or register to add a comment.