edited by
790 views
0 votes
0 votes

Given two sorted double linked list L1 and L2 of n elements each, which of the following are true?

(A) L1 and L2 can be merged into single sorted list in Θ(n) time.

(B) L1 and L2 can be merged into single sorted list in Θ(1) time.

(C) L1 and L2 can be merged into single sorted list in Θ(nlogn) time.

(D) L1 and L2 can be merged into single sorted list in Θ(n2) time.

edited by

1 Answer

5 votes
5 votes
  • WE can use same as merging procedure which will take O(m+n) . 

  • Both link list have n element then time complexity should be O(n+n)=O(2n)=O(n) so option a is right. 

Related questions

1 votes
1 votes
1 answer
2
meethunjadhav asked Jul 30, 2018
406 views
suppose merge sort takes 2 sec to sort a set of 64 keys then how much time will take to sort a set of 512 keys?here, ans is 24 sec how it is plz explain me.
1 votes
1 votes
2 answers
3
APOORV PANSE asked Jun 1, 2016
2,989 views
Consider the following c fragment : void DAA(n) { int i,j,k,x=0; for (i=1 ; i <=n ; i++) for (j=1 ; j <= i * i ; j++) { if ( j mod i == 0 ) for ( k = 1 ; k <= j ; k++) x=...
0 votes
0 votes
2 answers
4
Shivam_j asked Oct 16, 2022
672 views
Class B network on the internet has a subnet mask of 255.255.119.0 what is maximum possible hosts per subnet. Assuming Classfull Addressing Scheme