search
Log In
5 votes
1.9k 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?

  1. O(n)
  2. O(1)
  3. θ(n2)
  4. θ(n)
in Programming 1.9k views
1

both O(n) and θ(n) are correct.

0
Okay! i don't know why, but the answer key go with θ(n).

But i also clearly agree with both the options.
1
I think in general it should be O(n) as best case is O(1) answorst is O(n). But the question specifies that we have to add a node at last when the pointer is initially at start. So in best case and worst case both it comes O(n) that's why the answer is Theta(n).
0
in any case, you need to reach the last node to insert new node  so it cant be done by traversing  less than n nodes.so theta(n) is correct

1 Answer

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..
0
In both the case, as we have to ultimately traverse to the end of linked list the how it can become Theta(n)....???

Related questions

1 vote
1 answer
1
5.4k 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) .
asked Jul 4, 2018 in Algorithms arya_stark 5.4k views
0 votes
0 answers
2
251 views
struct node* foo(struct node* a, struct node* b) { struct node* result, *rec; if(a==null) return b; else if(b==null) return a; else { rec=foo(a->next,b->next); result=a; a->next=b; b->next=rec; return result; } }
asked Sep 17, 2018 in Programming Vaishnavi01 251 views
0 votes
1 answer
3
662 views
What kind of linked list is best to answer question like “What is the item at position n?” a) Singly linked list b) Doubly linked list c) Circular linked list d) Array implementation of linked list
asked Aug 19, 2018 in Programming pradeepchaudhary 662 views
1 vote
0 answers
4
586 views
Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node 'X ' from the list
asked Nov 25, 2017 in Programming saipriyab 586 views
...