retagged by
26,134 views
36 votes
36 votes

What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

  1. $\Theta(n)$
  2. $\Theta(n \log n)$
  3. $\Theta ( n)^{2}$
  4. $\Theta(1)$
retagged by

9 Answers

Best answer
53 votes
53 votes

"Inserting n elements into an empty linked list, list needs to be maintained in sorted order".

It is not mentioned if the "n elements" are given initially itself or we must insert one element at a time. 

  1. For the former case, we can just sort the initial n element array - can be done in $O(n \lg n)$ and then we'll insert them one by one to the linked list where the sorted order is always maintained. This process will take $O(n)$ and so the entire process can be done in $\Theta(n \log n)$ time.
  2. For the latter case, where we have to do insertion to the linked list one element at a time, the only way to ensure sorted order for the linkedlist is to follow insertion sort mechanism. This will take $\Theta(n^2)$ time in the worst case.

Since, the question is ambiguous in saying how the elements are presented, both options B and C should be given marks. Unfortunately official key considered later case only. Option C.

edited by
57 votes
57 votes

Each Insertion into a sorted linked list will take $\theta(n)$ and hence the total cost for $n$ operations is $\theta(n^2)$

Answer-(C)

15 votes
15 votes
One can easily challenge this question if original answer key comes out to be O(nlogn). What do you mean by elements here? It matters!!!

I know everyone of you would have assumed it to be Integer for sure. Imagine those elements are Strings of length O(n) each. Now the comparison of two strings itself would be O(n) and if you insert it in a normal fashion, the worst case would be O($n^{3}$). This is how actually one should think.

As options doesn't have O($n^{3}$), Now next question comes to mind is if i can sort the elements(Assuming Integer or floating point numbers) before hand and then try inserting one by one. Now comes the next question which sorting approach to use? comparison based or memory based(counting sort for e.g.). Lower bounds for comparison based is O(nlogn) and for memory based is O(n). So option A and B are both possible in that case.

If i think of online algorithm, i.e. the elements come one after the other and i need to insert them in the linkedlist. So in worst case using this approach one can get O($n^{2}$).

I would have personally gone with O($n^{2}$), as nothing is mentioned about space storage limitations and also making assumption about elements being Integers or float is not correct.
edited by
12 votes
12 votes

Answer. C. $\Theta (n^{2})$

Explanation

Question marks two key points here.

1. Sorted order is to be maintained.
2. 'n' elements to be inserted in a linked list.

Hence, for each element, we need to search it's correct position for every insertion. After the search is complete, insertion will take constatn time (i.e. mapping the correct pointers)

Now, considering the worst case where the inserting is made in last node (we'll have to scan entire list everytime)

For inserting first element, no. of elements scanned= 0
For inserting second element, no. of elements scanned = 1
For inserting third element, no. of elements scanned = 2
.
.
.For inserting nth element, no. of elements scanned = n-1

Total scans = 1+2+3+...(n-1)  //Thats an AP !

Total scans = $\frac{n}{2}((n-1)+1)$ = ~$n^{2}$

We can conclude is worst case as O($n^{2}$)

Answer:

Related questions

8 votes
8 votes
5 answers
1
Arjun asked Feb 12, 2020
18,577 views
The preorder traversal of a binary search tree is $15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree?$10,11,12,15,16,18,1...
27 votes
27 votes
2 answers
2
Arjun asked Feb 12, 2020
13,403 views
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?$\Theta (n^{4})$$\Theta (n^{2})$$\Theta (n^{2}\log n)$$\...
31 votes
31 votes
4 answers
3
Arjun asked Feb 12, 2020
7,387 views
Raman is confident of speaking English _______six months as he has been practising regularly_______the last three weeksduring, forfor, sincefor, inwithin, for
8 votes
8 votes
6 answers
4
Arjun asked Feb 12, 2020
5,740 views
His knowledge of the subject was excellent but his classroom performance was_______.extremely poorgooddesirablepraiseworthy