The Gateway to Computer Science Excellence
+1 vote
430 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) .
in Algorithms by Active (1.7k points) | 430 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).

Also before posting the question search it on google and on the site, someone might be already asked that question and got the answer it will save your time too. This question is already posted before here https://gateoverflow.in/170133/linked-list-time-complexity.

0
i didn't get this. bdw thnxx.

1 Answer

+3 votes
Best answer
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 by
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

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,645 questions
56,563 answers
195,733 comments
101,654 users