How does sorting a string in an array of strings and then sorting that array come out to be O(a*s(loga+logs))?
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.
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.