in Algorithms edited by
515 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.

in Algorithms edited by
515 views

3 Comments

consider them as normal elements in array where intially not sorted

therefore you required n . Log(n) time

if those two lists are already sorted you require only O(n) time
0
0
this case is same like merge algo of merge sort you are given two sorted list you just need to merge into single sorted list...with 2n elements so there would be n+n-1 comparison and movements would be 2n..so total time required would be O(n).
0
0
option A) O(n) is correct
0
0

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. 

2 Comments

option a is Θ(n). How is this correct?
0
0
minimum time is also order of n and max time is also order of n...so you can write your answer in terms of theta too
1
1

Related questions