+1 vote
526 views
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) .
| 526 views
0

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

0
i didn't get this. bdw thnxx.

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.
by Active (4k points)
selected
0
Got it... Thnxx Sir!!
0

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.

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