retagged by
26,133 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

6 votes
6 votes

FOR WORST CASE: Consider decreasing order sequence say {5,4,3,2,1}

We have 5 as the Starting node..

Then we insert 4 (No of comparisons required to insert 4 in linked list = 1) 

Then we insert 3 (No of comparisons required to insert 3 in linked list = 2)

and then we add 2,1 in that order and comparisons required for inserting are 3 and 4 respectively.

 

 

 

 

 

So total comparisons done is (for 5 keys): 1 + 2 + 3 + 4 = 10

Similarly, for n keys we have

1 + 2 + 3 + 4 + 5 + ................... N-1

Which equals to   N(N-1) / 2             

So, complexity is O($n^2$)     

 

                                                                                                                                                      

4 votes
4 votes
I have assumed that keys are integers or floating points.

Even if we do online sorting(maintain sorted order of linked list after each insertion) we can do that in $O(nlgn)$ time.

Idea is to use Balanced BST to keep track of location in linked list where each key resides. So whenever new key is to be inserted we insert it into BST and then the parent of newly created node is the node where we will find pointer to linked-list slot which we can use to insert new element in constant time.

So we can do each insertion in $O(lgn)$ time.
reshown by
1 votes
1 votes
We need to search for the correct relative position of the element to insert.

In linked list it will take O(n) for each element.

For  'n' elements = n* O(n) = O(n*n)
1 votes
1 votes
Suppose we have a $head$ pointer and a $tail$ pointer.

In worst case, each element is to be inserted in the $middle$ of the list. Therefore time taken is $\Theta(n/2)$ $\approx$ $\Theta(n)$. Then for inserting $n$ elements we need $\Theta(n*n)$ =  $\Theta(n^{2})$
Answer:

Related questions

8 votes
8 votes
5 answers
1
Arjun asked Feb 12, 2020
18,571 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,395 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,386 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,736 views
His knowledge of the subject was excellent but his classroom performance was_______.extremely poorgooddesirablepraiseworthy