530 views

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.

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
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).
option A) O(n) is correct

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

option a is Θ(n). How is this correct?
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 vote