edited by
1,390 views
3 votes
3 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)$
edited by

2 Answers

Best answer
4 votes
4 votes
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
selected by
0 votes
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)$

Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,641 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
1 votes
1 votes
3 answers
3
0 votes
0 votes
0 answers
4