I have a list of words, and a lot of posts. I have to check if any of those words are present in the post, if so, save it, and then go to the next, and so on.
I can change the list of n words in an hashmap so when I'll check I'll have O(1), but I have still to go through all the words in the single post [O(n)], and then to all the posts [O(n^2)].
Any suggestion to improve this?
Usually I wouldn't bother, but the number of posts is massive.
That's mostly right. You can't beat O(n + m) where n is the number of words in all of the posts and m is the length of target words. We assume O(1) to look up each word in the set/hash of target words m and O(m) to build the set.
But O(nn) doesn't look right because the size of the posts isn't quadratic and there's no relationship between the number of words in posts and the number of posts.
You could call it O(num_target_words + num_posts * max(num_words_in_post)) but this seems like an awkard way to characterize the problem that's mostly dependent on words, not on posts. So just O(n + m) seems clearest.
If m is constant and/or the set construction is guaranteed non-expensive, we can disregard it and just call it O(n). But maybe you have a huge bucket of potential words and just a few posts, in which case m dominates.
