Register
Dark Mode

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 4

in DS recategorized by
538 views
9 votes
9 votes
Given a circular, doubly-linked list whose contents are sorted in ascending order, what is the run-time complexity for inserting a new element into the list so that it remains correctly sorted? (Including the time required to search for the element’s correct position.)
  1. $O(1)$
  2. $O(\log \text{N})$
  3. $O(N)$
  4. $O(\text{N}^{2})$
in DS recategorized by
by
538 views

4 Comments

by
edited by

I think binary search can be applied to linked lists (even the singly ones). Say I have a SLL

1  → 3 → … → 100 and I want to insert 2. Then I can traverse till the mid point taking N/2 time (assuming I maintain a global count variable) and the value there (50) is greater than than the value to be inserted (2) so I keep the left pointer as is and make the right pointer point to node containing 49.

Effective SLL now is: 1 → 3 → … → 49.

Again same steps, the time to traverse till mid (25) is (N/2)/2 = N/4.

So on and so forth the effective time to find the location to insert 2 will be N/2 + N/4 + N/8 .. = $\log _{2} n$. Inserting a new node is O(1) anyways.

0
0
by
I calculated and it comes to be O( N) . Can you confirm?
0
0
by

@Yuvraj Raghuvanshi how n/2 + n/4 + n/8 + ... + 1 = log n ??

And what you're doing is equivalent to linear search.

1
1
by
Ah yes I made a mistake. Comparisons will be O(log n) traversal still is in O(n)
2
2

1 Answer

7 votes
7 votes
It’s better to take the worst case possible

Assume we have 1<->2<->3<->4 in the list

new node to be added is say 5

so to maintain the linked list in the sorted order we have to go to the last node to insert this new node

which takes O(n) time if we n elements

so option c is correct
edited by
by

5 Comments

by
Your answer is about singly linked list. The question however takes doubly circular linked list
0
0
by
Correct

i will edit the arrows

but will it make a difference??

what do you think
0
0
by
Yes this seems correct.
0
0
by
In this question we  are using liner – serch algorthim(check each element one by one) so O(n) ?
0
0
by
edited by
Not only linear search you can also use binary search but the results would be same as in binary search also traversing takes O(n)
2
2
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

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

Subjects

Developed by Chun
Link Copied!