Test by Bikram | Data Structures | Test 2 | Question: 7

Question

You are given a linked list, L, and another linked list, P, containing integers, sorted in ascending order. The operation print_lots(L,P) will print the elements in L that are in positions specified by P. For instance, if $P = 1, 3, 4, 6$, the first, third, fourth, and sixth elements in L are printed. If you write the routine function print_lots(L,P) where you should use only the basic list operations.  The running time of your routine function is ______________ ?

• A. $O( n^2 )$
• B. $O(n)$
• C. $O(n \log n)$
• D. $O(\log n)$

Comments

I feel its A or B .

But acc.to key its D . how ?

---

sir i got  b.........plz explain how its D

---

corrected my mistake, it is option B = > O(n)

that list is sorted already so only one time we need to traverse thts come O(n) is answer .

---

and another linked list, P, containing integers, sorted in ascending order

I am confused with this statement. Anyone can pls explain whether only P is sorted or L is also sorted

Answer 1

Both link list are sorted already. so no need to traverse any link multiple time. in link list access and traverse TC is O(n). what here we have to do is start traversing both list from initial node. as we move forwad in P list we get the positions in L list in asecending order, at which node we find required point and print it. as lists are sorted no need to traverse multiple time. so only in one traverse we get the output. so if list haas n elements, TC is O(n). so answer should be option B

Comments

Thank You for this answer. :)

---

if function is called N times then we can use binary search each time and hence the complexity will be O(NlogN). I thought this way!

---

i thought P is unsorted so thought that we need time for sorting that :/

Answer 2

Whatever P's contents are, we have to print L's content of that node.

Since P is sorted in increasing order, hence for any print action we never have to go back in L. In just one careful traverse we can do this.

So $O(n)$

---

A little more details:-

Assume P's contents are 3, 16, 49 and 200. (sorted in increasing order)

We have to print the contents of L located at node 3, node 16, node 49 and node 200.

So, max we need to go to 200, and this can happen in a single pass.

 

So, $O(n)$ // to traverse P

$+ O(1)$ // to traverse upto the last element specified by P, which will be some constant.

=> $O(n)+ O(1)=O(n)$