Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

The_mysterio's blog

By The_mysterio, history, 6 years ago, In English

Hello Everyone, This is a just a thought that came to my mind. Normally we sort numbers with the time complexity of n log n where n is the number of numbers present in the array.Same for a list of characters. However, for a list of given strings,let us say all the strings are of equal length and that length is m. For comparing two strings we need at most iterations.So in that case , isnt the complexity (n^2)*m ???Because the recurrence relation will be T(n)=2*T(n/2)+ n*m---> where merging takes m units of time for each comparison of two strings... If anyone can clarify this doubt, It will be of great help.. Thanks in advance

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

If you search the title of your blog you get this StackOverflow article, which should answer your question. Took me maybe a minute to find.