The Gateway to Computer Science Excellence
+2 votes

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

  1. $O( n^2 )$
  2. $O(n)$
  3. $O(n \log n)$
  4. $O(\log n)$
in Programming by Veteran (75k points)
edited by | 124 views
I feel its A or B .

But 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

2 Answers

+4 votes
Best answer
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
by Active (3.6k points)
selected by
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 :/
0 votes

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

by Loyal (7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,405 answers
105,465 users