Asymptotic time complexity to add a node at the end of singly linked list.

Question

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) .

Comments

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.

---

i didn't get this. bdw thnxx.

---

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)

Answer 1

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.

Comments

Got it... Thnxx Sir!!

---

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.

---

edited..deleting or adding after reaching the last node will take constant time