recategorized by
3,428 views
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?

  1. O(n)
  2. O(1)
  3. θ(n2)
  4. θ(n)
recategorized by

1 Answer

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

Related questions

1 votes
1 votes
1 answer
1
3 votes
3 votes
2 answers
3
Vishal Goyal asked Sep 26, 2016
677 views
Two linked lists having n and m elements are stored in sorted order. What is the worst case complexity of program to print common elements of two lists ?$\begin{align*} &...