The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
166 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 in Algorithms by Junior (947 points) | 166 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.
answered by Active (3.9k 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

0 votes
1 answer
1


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

44,235 questions
49,719 answers
163,886 comments
65,834 users