How does sorting a string in an array of strings and then sorting that array come out to be O(a*s(loga+logs))?

Question

In the image I do not understand where the extra O(s) comes from when the array of strings are being sorted. I get that sorting the array of string will be O(a log a), I can't understand why we have to add in O(s) as well.

In my mind, O(a log a) has taken care of sorting off all the strings in the array of strings.

Answer 1

Got stuck on the same example! Remember that optimally it takes nlogn time to sort an array of n characters. For the final sort if we assume that each string in the array is of length 1 then we're again just sorting a characters so we get the aloga term, however the worst case length of each string is s so you need to do aloga comparisons s times.

Answer 2

In the image you ask "why add?" Well, they are independent operations, one that sorts each of a strings the length of each is s, and that's O(a * s log s), and one that sorts the array of a strings, the length of each is s to count potential comparisons between each two strings, that's another O(a * s log a). Independent operations means "add". Adding gives O(a * s log s + a * s log a), which is what you got when you extract out the common factors.

Answer 3

Understand in such a way that when you're sorting an array of characters/numbers, you can sort that array based on simple comparisons of two index elements and complexity will be O(N*log(N)) where N is the length of array.

What happens when you start sorting an array of string?

array[0] = "rahul" and array[1]= "raj"

If you have to sort the above two indexes lexicographically (you can't simply compare two strings like numbers), you need to compare character wise. So it will run Math.max(array[0].length(), array[1].length()) times. From here that extra s is coming in O(s*a log(a))