Brian Jones Jr. wrote:
Can we first start with how they figured out how sorting each string is O(s log s)?
Campbell Ritchie wrote: Interesting question Please tell us where it comes from, so as to avoid copyright problems.
Let's change that to O((n)log(n)) to maintain the precedence of the multiplication.
A few minutes ago, I wrote:. . . O(nlogn) where
n = a × s . . .
Campbell Ritchie wrote:It will actually reduce to O(nlogn) if I try a bit of jiggery‑pokery.
Your String comparisons will run in linear time O(n) and that is a lower complexity than O(nlogn), so let's ignore it.
Campbell Ritchie wrote:If the Strings are all s characters long, you are going to do our sorting in O(nlogn + s) time and we can forget the s.