retagged by
1,006 views
2 votes
2 votes
Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity?
retagged by

3 Answers

2 votes
2 votes
First sort both arrays and then combined into a single array, complexity = m log(m) + n log(n) + (m+n)

First combine into a single array and then sort the combined array, complexity = (m+n) log (m+n)
0 votes
0 votes

Simply combine both arrays then resultant array will have m+n elements.

Then apply best sort method on O(nlogn) which will give here (m+n)log(m+n)

So here by combining and then sorting is efficient.

0 votes
0 votes

We can sort both arrays using Linear sort and Linear sort take O(n+k) time and after sorting them we can merge them into one array. For merging O(n) time taken so total time complexity will be:-

2.(O(N+k)) (sorting) + O(n)(for merging)  so it is some how equal to O(n).

Related questions

333
views
1 answers
0 votes
Mrityudoot asked Mar 7
333 views
For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort ... the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?
742
views
2 answers
0 votes
_Madhuri asked Oct 9, 2021
742 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
556
views
0 answers
0 votes
Prince Sindhiya asked Aug 23, 2018
556 views
i mark the option D) but answer is A)
886
views
2 answers
1 votes
Ravi Dubey asked Aug 2, 2018
886 views
Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.