What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity? Let's assume I have a list of some words found in the English dictionary:
[&quot;hat&quot;, &quot;assume&quot;, &quot;prepare&quot;, &quot;cat&quot;, &quot;ball&quot;, &quot;brave&quot;, &quot;help&quot; .... ]
I want to sort these words (which are n in number) in a way, such that they are ordered based on their length, but if 2 words have the same length, they are ordered alphabetically.
What is the time complexity of this sorting operation?
Would it be fair to say that the complexity is just O(nlogn) and not take into consideration the length of the strings? If the largest length is S, can the complexity also involve a factor of S?
This algorithm requires at most $O(n \log n)$ string comparisons, assuming you use a suitable sorting algorithm.
If strings are at most $S$ characters long, each string comparison can take up to $S$ operations.  So, the worst-case running time could be as large as $O(S n \log n)$.
If the size of the character set is constant, then it is possible to solve your problem in $O(n(S+\log n))$ time with a slightly different algorithm: compute the length of each string ($O(nS)$ time), sort the strings by length ($O(n \log n)$ time), then for each length, use radix sort on the strings of that length ($O(nS)$ time).