GATE CSE 2020 | Question: 16

Question

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?

• A. $\Theta(n)$
• B. $\Theta(n \log n)$
• C. $\Theta ( n)^{2}$
• D. $\Theta(1)$

Comments

True. Although, the question didn't explicitly mention whether it wanted the linked list to be maintained in sorted order after every insertion or after all n elements had been been inserted.

---

yeah, elements need to be maintained in sorted order means you have to just sort, it is not necessary to insert 1 by 1. So you can sort before insertion. O(nlogn) should be the answer.

---

Ambiguous Question

Answer 1

"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.

Comments

@princeit07 Considering that you are asking about the first case as mentioned by @Arjun Sir:-

It is not mentioned if the "n elements" are given initially itself 

So considering that we are given the ‘n’ element array before hand, first sort the ‘n’ element array. It takes $O(nlogn)$. Then insert the elements one by one into the linked list. It takes $O(n)$.

Overall T.C: $O(nlogn)$

But since it is not mentioned, it might also happen that they arrive one by one. In that case T.C. = $O(n^2)$.

Both are possible as the question is bit ambiguous.

---

Since question is asking about worst case, so the worst case is when all the inputs are not present initially which leads to worst case time complexity of $\theta$(n$^{2}$).

---

Hello sir, the question is not ambiguous, i think you missed the part where it says, that you need to insert n elements into an “Empty- linked list”.

Answer 2

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)

Comments

Exactly. Anyone please verify and any one of the moderators please look into this arjun sir bikram sir or anyone please.

---

As mentioned by @Ruturaj in his answer below, the question seems ambiguous.

---

@Arjun sir please look into this question.

Answer 3

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.

Comments

@Ruturaj Mohanty

i agree with u that thinking process matters for interview.there it is imp to ask ques and clear your doubt before writing code.but how can u assume that the elements can be string of order n by yourself.unless mentioned we can assume it to be constant size int or float or constant size string.otherwise int can also be of variable length,can't they?

Don't feel offended,i didn't want to argue with u.just telling my perspective 🙂🙂

---

int can be also of variable length? really ???

Moreover i didn't say to challenge the question just because of the term element in it. That i wrote just to help gate people think how here at iit people think so that they don't score a zero here.

If you don't know the type of elements then how can you allocate space for that type beforehand and then do sorting? In GO answer key O(nlogn) was given. So i said one can easily challenge if original answer key comes out to be O(nlogn).

I am not offended by your words. I am glad that you gave a thought my writing.

---

@Ruturaj Mohanty

bro i dont know whether it is right to call variable length int or not but there are variable length no. And even variable length binary no. You much have heard about karatsuba algorithm of multipling 2 large no. Of size n

you may refer this

https://www.quora.com/What-is-the-fastest-algorithm-for-multiplication-of-two-n-digit-numbers-1

Answer 4

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}$)