1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

# A list of n strings, each of length n, is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is

A
0(n log n)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
B
0(n2 + log n)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
C
0(n2)
No worries! Weâ€˜ve got your back. Try BYJUâ€˜S free classes today!
D
0(n2 log n)
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution

## The correct option is D 0(n2 log n)The recurrence tree for merge sort will have height n and 0(n2) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes 0(n) time in worst case). So time complexity of this merge sort will be 0(n2 log n) .

Suggest Corrections
1
Join BYJU'S Learning Program
Related Videos
Evaluation of Determinants
MATHEMATICS
Watch in App
Join BYJU'S Learning Program