retagged by
905 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

0 votes
0 votes
2 answers
2
_Madhuri asked Oct 9, 2021
634 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
0 votes
0 votes
0 answers
3
1 votes
1 votes
2 answers
4
Ravi Dubey asked Aug 2, 2018
829 views
Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.