retagged by
421 views
1 votes
1 votes
Let there are n elements in array and number of sorted subarray is log n of size n/ log n each then

what is the time complexity to sort given array
retagged by

1 Answer

Best answer
1 votes
1 votes

Merge procedure takes = $O(m+n)$ time where $m$ and $n$ are sorted subarray sizes

Total complexity = (No of levels) * (Each level work) = $n\cdot \log_2 \left ( \log n \right )$

selected by

Related questions

1 votes
1 votes
0 answers
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
3 answers
3
0 votes
0 votes
1 answer
4
Deepalitrapti asked Sep 11, 2018
313 views