3 ms·
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
by 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.