The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
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 Active (2.2k points)
edited by | 193 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 (57.4k points)
selected by
+1 vote
answered by Veteran (18k points)
that will be the best case i think:max(m,n)
yes, it should be m+n. Editing.

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

28,834 questions
36,689 answers
34,641 users