The function Compare2strings will take input two strings and output the lexicographic order in which they should appear
compare2strings(String s1, String s2)
{
int ptr=0;
while( s1[ptr] = = s2[ptr] && ptr < n )
{ ptr++;
}
if( s1[ptr] < = s2[ptr]
return (s1,s2)
else if( s1[ptr] > s2[ptr]
return (s2,s1)
} // This function takes worst case O(n) to compare two strings.......
MergeSort(Sequence 1.......nth strings)
{
if(Single string is given as input)
return string
else
{
MergeSort(Sequence 1,2,3.....n/2th strings)
MergeSort(Sequence (n/2+1),(n/2+2).......nth strings)
Merge(Sequence 1,2,3.....n/2th strings, Sequence (n/2+1),(n/2+2).......nth strings )
}
}
Merge(Seq1 , Seq2)
{ Worst case number of string comparisons among strings = O(n + n-1) = O(n)
with each comparison O(n) using compare2strings function
Merge cost in worst case = O(n).O(n) = O(n^2)
}
T(n) = 2T(n/2) + O(n^2)
Master theorem T(n) = O(n^2)
so B, C, D all are answers. Maybe that is the reason marks are awarded to all