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

327
views
1 answers
0 votes
Mrityudoot asked Mar 7
327 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$)?
740
views
2 answers
0 votes
_Madhuri asked Oct 9, 2021
740 views
The complexity of comparison based sorting algorithm is (nlogn) .How?
552
views
0 answers
0 votes
Prince Sindhiya asked Aug 23, 2018
552 views
i mark the option D) but answer is A)
884
views
2 answers
1 votes
Ravi Dubey asked Aug 2, 2018
884 views
Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.