3 ms·

> Some candidates say that sorting is going to be the bottleneck, because it’s O(N log N) rather than the input processing, which is O(N). However, it’s easy to

> Some candidates say that sorting is going to be the bottleneck, because it’s O(N log N) rather than the input processing, which is O(N). However, it’s easy to forget we’re dealing with two different N’s: the total number of words in the file, and the number of unique words. I don't see how that changes anything. There's a reason we use Big O rather than other notations. Their answer would still be correct.

deleted 4y ago
[deleted]
kragen 4y ago
input processing is o(n), sorting the unique words is o(m log m) whether o(m log m) is bigger or smaller than o(n) depends on the relationship between n and m in the case used by another poster in this thread, concatenating some large number of copies of the bible, m is constant, so o(m log m) is o(1) in another possible case where the corpus is generated uniformly randomly over all possible words of, say, 20 letters, though in theory o(m log m) is o(1), over a practical range it would be o(n log n) more typically m is proportional to some power of n depending on the language; for english the power is 'typically between 0.4 and 0.6' as it turns out o(√n log √n) is less than o(n) a totally different issue is that big-o notation doesn't always narrow down where the bottleneck is even if you calculate it correctly because n is never arbitrarily large and so the bottleneck depends on the constant factors
- nkozyra 4y ago
  > a totally different issue is that big-o notation doesn't always narrow down where the bottleneck is even if you calculate it correctly because n is never arbitrarily large and so the bottleneck depends on the constant factors Yeah I think this is part of my point, in that theoretical best, average and worst case scenarios can be useful in isolation but rarely tell the whole story. In the worst case, every word is unique and is equal to word count and it's a standard sorting issue.
burlesona 4y ago
No. Big O tells us the theoretical best case for how the compute time will increase as the input size increases for a given algorithm. It does not say anything about the performance of a specific program on a specific input. The author’s point is that if we have two different inputs A and B, and A is sufficiently smaller than B, then the runtime of B will dominate the program. This would be true even if we have to operate on A with a very slow algorithm. For example suppose you have some extreme scenario where you have to do three coloring on A and then find the minimum value of B. The runtime would be O(2^A) + O(B). Just plug in numbers and you can see that if B > 2^A then B takes longer even though that algorithm is much faster. If you suppose B is always much larger than 2^A, then B is your bottleneck.
bufferoverflow 4y ago
It really depends on the number of unique words in the input file. If it's all unique words, sorting can become the bottleneck.

deleted 4y ago

[deleted]

kragen 4y ago

input processing is o(n), sorting the unique words is o(m log m) whether o(m log m) is bigger or smaller than o(n) depends on the relationship between n and m in the case used by another poster in this thread, concatenating some large number of copies of the bible, m is constant, so o(m log m) is o(1) in another possible case where the corpus is generated uniformly randomly over all possible words of, say, 20 letters, though in theory o(m log m) is o(1), over a practical range it would be o(n log n) more typically m is proportional to some power of n depending on the language; for english the power is 'typically between 0.4 and 0.6' as it turns out o(√n log √n) is less than o(n) a totally different issue is that big-o notation doesn't always narrow down where the bottleneck is even if you calculate it correctly because n is never arbitrarily large and so the bottleneck depends on the constant factors

nkozyra 4y ago
> a totally different issue is that big-o notation doesn't always narrow down where the bottleneck is even if you calculate it correctly because n is never arbitrarily large and so the bottleneck depends on the constant factors Yeah I think this is part of my point, in that theoretical best, average and worst case scenarios can be useful in isolation but rarely tell the whole story. In the worst case, every word is unique and is equal to word count and it's a standard sorting issue.

burlesona 4y ago

No. Big O tells us the theoretical best case for how the compute time will increase as the input size increases for a given algorithm. It does not say anything about the performance of a specific program on a specific input. The author’s point is that if we have two different inputs A and B, and A is sufficiently smaller than B, then the runtime of B will dominate the program. This would be true even if we have to operate on A with a very slow algorithm. For example suppose you have some extreme scenario where you have to do three coloring on A and then find the minimum value of B. The runtime would be O(2^A) + O(B). Just plug in numbers and you can see that if B > 2^A then B takes longer even though that algorithm is much faster. If you suppose B is always much larger than 2^A, then B is your bottleneck.

bufferoverflow 4y ago

It really depends on the number of unique words in the input file. If it's all unique words, sorting can become the bottleneck.