The Gateway to Computer Science Excellence
+5 votes
991 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 by Active (2.7k points) | 991 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..
by Active (3.6k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,314 answers
198,358 comments
105,085 users