Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

Question

The questions is:

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

The solution is given as below:

What i find peculiar in the above solution is this: "You should also take into account that you need to compare the strings. Each string comparison takes O (s) time.There are O (a log a) comparisons, therefore this will take O (a*s log a) time."

What do we need the comparisons for?

It would take s log s time to sort a string. Say there a strings hence the total time taken would be a*s log s

Now the problem has shrunken down to simply sorting a given array which you can do in a log a time, hence the total time taken is a*s log s + a log a = a (s log s + log a)

Where did I go wrong in my thought process?

The question is taken from the book, Cracking The Coding Interview

Answer 1

Sorting a list of numbers assumes that comparisons occur in O(1) constant time, giving the nlogn complexity, in terms of number of comparisons. However when we are sorting an enumerable whose members require a time x to compare,the run-time becomes xnlogn. This is because we are performing an action that requires x time, nlogn times.

But, I must also argue, that strings are a direct bijection to base 26. Since we consider comparison in base 10 to occur in constant time, there is no reason not to extend this to the strings which are essentially numbers in base 26. This really depends on the implementation of the string comparing mechanism. So, depending on how string comparison is done, we end up with two possible runtimes.

Yours is correct, if and only if we assume strings to be compared as numbers in base 26, and assuming that can be done in constant time.

Otherwise, sorting in general takes (Comparison time) x nlogn