 Win a copy of Machine Learning with R: Expert techniques for predictive modeling this week in the Artificial Intelligence and Machine Learning forum!

Steven Lybeck

Greenhorn
since Mar 05, 2019
Cows and Likes
Cows
0
In last 30 days
0
Total given
0
Likes
0
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Scavenger Hunt Ranch Hand Scavenger Hunt Greenhorn Scavenger Hunt

Recent posts by Steven Lybeck

Sorry for the double post - I just wanted to edit to add: I agree with your ultimate conclusion that the notation could be further reduced from the book's answer O(a*s(log a + log s)) to: O(a*s*log(a*s))

The Cracking the Coding Interview book takes pains to remind that your complexity notation has to reference all inputs that can scale independently, so in this example it must take into account both 's' (length of strings) and 'a' ( length of array. I guess folks would be satisfied with O(n*log(n)) as long as you also make it clear that n=a*s
7 months ago
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:

O(n*log(n)) - 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.
7 months ago