GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
157 views
Two linked lists having n and m elements are stored in sorted order. What is the worst case complexity of program to print common elements of two lists ?

$\begin{align*} &A. \ \ O(n) \\ &B. \ \ \text{max}(m,n) \\ &C. \ \ \text{min}(m,n) \\ &D. \ \ m+n \end{align*}$
asked in Algorithms by Junior (947 points)  
edited by | 157 views

As in worst case may be we ended up by comparing every element of both the list in alternate manner hence , it would be O(m+n)

2 Answers

+4 votes
Best answer
O(m+n) similar to combine step of merge sort.
answered by Veteran (45.6k points)  
selected by
+1 vote
Max(m,n)
answered by Veteran (14.9k points)  
that will be the best case i think:max(m,n)
yes, it should be m+n. Editing.

Related questions



Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users