GATE Overflow | Data Structures | Test 1 | Question: 24

Question

You are given a linked list, $L$ of $n$ integers, and another linked list, $P$, of $k$ integers where $k <<< n$. $L$ is sorted in ascending order but $P$ is not necessarily sorted. The operation $\text{print_lots}(L,P)$ will print the elements in $L$ that are in positions specified by $P$. For instance, if $P = 2, 1, 3, 6$, the second, first, third, and sixth elements in $L$ are printed in the same order. If you write the routine function $\text{print_lots}(L,P)$, the best running time of your routine function will be (assume $O(n)$ auxiliary space is available)  ______________ ?

• A. $\Theta(n)$
• B. $\Theta(n \log k)$
• C. $\Theta(n k)$
• D. $\Theta (n k\log k)$

Answer 1

It looks O(NK) ?

But, it is given that k<<<N and auxiliary space of O(N) is there.

So, sort P array in O(K log K) and copy/store the order of P array in an auxiliary array, in which we have to print the elements of L.

Hence, in one traversal of head pointer throughout the list, this can be done.

Total Time Complexity = O(K Log K)  +  O(K)  + O(N) = O(N) as k<<<<N

Comments

@Arjun sir :--> When there are questions related to time complexity like this, Is it appropriate to go for auxiliary space, if we can optimize TC. If it is explicitly given, then it is right, otherwise is it right ?

but since you made it clear explicitly that auxiliary space is there, so TC was minimized . Otherwise, i would have opted for O(nk).

---

Unless specified it becomes ambiguous. Still, I guess we can use auxiliary space if it gives better time complexity.

---

Okk sir, 

I having having a doubt in this question https://gateoverflow.in/blog/281

If sorting is done, then O(N Log N) is good ,

but if we use hash table for this, it can be done in O(N) . Then, what is best here ? 

Edit : Sir, i think that for worst case, they are assuming that hash table can give WC TC = O(N²) ,due to linked list ?

---

I would go for $O(n)$ there. But I have a bigger problem if questions are posted as blogs :(

---

Sir, Can we remove that question from there and move to Q/A section ?

---

yes, I'll do so. As of now, there is no automatic way to do so.

---

@Arjun sir

can we use this auxilary space as Array ??

---

Why not just use the O(n) space as an auxillary array, copy all linked list elements in the array in O(n) time. Now any element can be accessed directly.

Answer 2

We are given with the linked list $L$ which contains $n$ elements. It is also mentioned that we have $\theta (n)$ space.

One thing that we can do is, traverse the whole list $L$, and save it to an array of size $n$, hence using that auxiliary space of $\theta (n)$. This will take $\theta (n)$ time.

Now traverse the list $P$ having $k$ elements, and for each element in $P$ print the element in that index in our array.

Say $P$ is $2,1,6$. Then we start traversing $P$, first is $2$, so we print $2nd$ element of our array, then $1st$ element, and then $6th$ element. And so on. This will take $\theta (k)$.

The whole procedure will take  $\theta (n) + \theta (k)$, ie $ = \theta (n)$. Since, $k<<<n$.

Comments

I don't know why everybody is discussing so much on the best answer chosen when this is the simplest approach.

Answer 3

For each entry in P we have to search Linked List (L).
No of entries in P is 'k' and average search time in Linked List is O(n).

Total time is k*O(n) i.e. O(kn).
Sir why answer is 'n' why not 'nk' ?

Comments

awaiting!

---

is this method correct? Traverse linked list L and copy the elements in the array and since linked list is sorted in ascending order, array will also be sorted. Then index the array for the positions specified by the linked list p and print them. It will take O(n) time.

---

@arjun sir i got the solution of Risabh Gupta but i didn't get the best answer if we sort it then it Is O(klogk) and for copy into auxiliary space it will take O(k) but then how we can print the list elements in one traversal of head pointer ?