0 votes 0 votes We are having 4 sorted sub-lists of size n/4, What is the time complexity to merge them in a single sorted list? Algorithms time-complexity algorithms + – Crackca asked Nov 20, 2021 Crackca 308 views answer comment Share Follow See 1 comment See all 1 1 comment reply LRU commented Nov 21, 2021 reply Follow Share O(nlogn) 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes @Crackca It is based on the divide and conquers approach. Therefore, the time complexity of Merge Sort is θ(nlogn)... 1. https://gateoverflow.in/146006/Sorted-list 2. https://gateoverflow.in/16103/The-time-complexity-of-producing-a-sorted-list wer 123 answered Nov 20, 2021 wer 123 comment Share Follow See 1 comment See all 1 1 comment reply Crackca commented Nov 21, 2021 reply Follow Share It should be O(n). Take n = 40000000 (4 crore) so there are 4 sub lists with n/4 = 10000000 (1 crore) so the number of comparisons required = 80000000 – 3 = 80000000 (approximately) If we take T.C. = O(n*logn) ==> 10000000 * log(10000000) = 10000000 * 23 = 23 Crore If we take T.C. = O(n) ==> n = 8 Crore So, T.C. = O(n) is more close to the number of comparisons. So, O(n) should be the answer. 0 votes 0 votes Please log in or register to add a comment.
