Dark Mode

5 votes

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) ______________ ?

- $\Theta(n)$
- $\Theta(n \log k)$
- $\Theta(n k)$
- $\Theta (n k\log k)$

6 votes

Best answer

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

5 votes

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

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

0 votes

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' ?

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' ?

0

yes, we can do a single traversal of the list $L$ and print the elements in indexes specified by $P$ provided $P$ is sorted. This is just straight forward rt?

But here, $P$ is not sorted- we can sort it. But, even then we have to ensure the order of printing is not affected by sorting. For this we need auxiliary space and some rearrangements. You can try this :)

But here, $P$ is not sorted- we can sort it. But, even then we have to ensure the order of printing is not affected by sorting. For this we need auxiliary space and some rearrangements. You can try this :)

0

0

0