Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?

The Gateway to Computer Science Excellence

+35 votes

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

- $O (n \log n) $
- $ O(n^{2} \log n) $
- $ O(n^{2} + \log n) $
- $ O(n^{2}) $

+1

Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?

+19

[1] In merge sort of array of length "n" you get a tree of height log(n).

[2] If single element of array is just an integer then at any level of tree, in worst case there will be n comparisons in merge process.

[3] Now if the single element of array is itself an array of size "m" then in order to find larger of 2 elements you need to compare all the m elements.

[4] So at any any level there are n comparisons and each comparison costs "m", so total nmlog(n)

[2] If single element of array is just an integer then at any level of tree, in worst case there will be n comparisons in merge process.

[3] Now if the single element of array is itself an array of size "m" then in order to find larger of 2 elements you need to compare all the m elements.

[4] So at any any level there are n comparisons and each comparison costs "m", so total nmlog(n)

+1

In general merge sort contains "n" elements with "log n"levels and in each level "n" data movements so TC is "n logn"

-->here we have "n" strings each of length"n"and each level we have n*n data movementa so "n^2 logn"...

-->here we have "n" strings each of length"n"and each level we have n*n data movementa so "n^2 logn"...

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,309 answers

198,337 comments

105,024 users