I realize this is over 2 years old now, but I'm going through the Cracking the Coding Interview book and found my way to this forum as I didn't immediately understand the explanation given in the book. Having dug into it a bit, I think I get it now.
And I think there's one slight mistype in Campbell's post:
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.
It seems like we *can't* drop the O(n)
term for string comparisons, since it's actually an O(s)
term on an independent input ('s' for length of the strings) rather than 'n' for the length of the array.
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.
This is my first time learning how to analyze algorithm complexity, but I believe this is the understanding to have here:
- This is the upper bound of 'number of operations' in the sorting algorithm that we run to sort the array. But how long does each operation take? Well, it's a comparison operation that depends on the length of the string
in each element of the array. So, for each comparison, we have an operation: O(s)
Therefore to describe the complexity of the array-sorting portion of this problem we should multiply instead of adding: O(s * (n * log(n)))
Sorry if this reads as a pedantic response years later - like I said, I'm just learning this stuff and trying to make sure I really understand it.