The Gateway to Computer Science Excellence
0 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?
a) O(1)
b) O(n)
c) θ(n)
d) θ(1)


in Programming by Active (1.2k points) | 41 views

It should be C.

O(n) means the time complexity for the given function is not more than c*n time where c is a constant.

But adding node at the end of list needs the whole list to be traversed and there is no upper or lower bound to it. It is exactly equal to c*n. So 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.

Answer would be 4

3 is theta(n) ..

1 Answer

0 votes
Theta(n) would be more correct one as average  and worst case both are  covered  here
by Loyal (5.7k points)
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,384 answers
105,342 users