since Mar 05, 2019

Cows and Likes

Cows

Total received

0

In last 30 days

0

Total given

0

Likes

Total received

0

Received in last 30 days

0

Total given

0

Given in last 30 days

0

Forums and Threads

Scavenger Hunt

Ranch Hand Scavenger Hunt

Greenhorn Scavenger Hunt

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**

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

4 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:

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.

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.

And I think there's one slight mistype in Campbell's post:

Campbell Ritchie wrote:It will actually reduce to O(n

logn) 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

Campbell Ritchie wrote:If the Strings are all

scharacters long, you are going to do our sorting in O(nlogn + s) time and we can forget thes.

This is my first time learning how to analyze algorithm complexity, but I believe this is the understanding to have here:

Therefore to describe the complexity of the array-sorting portion of this problem we should multiply instead of adding:

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.

4 months ago