# Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list?

I can't think of another way to do this other than just going through each element in the list and checking whether it's the word I want.

• You can't do that faster. There is no way you can conclude that a word is not in the list without looking at all the input. A running time of $n$ for input size $n$ is optimal. – AstridNeu Sep 18 '19 at 21:17
• If you need to solve the problem multiple times with the same dictionary but different words you can use a Trie to solve the problem in linear time in terms of the input. – Marcelo Fornet Oct 18 '19 at 5:33
• What is the exact definition of your problem? Is the list, the word, or both part of your input? Do you need to solve the problem only once or for multiple lists (same word) / words (same list)? – Steven Oct 18 '19 at 17:37

It really depends on what data structure you want to use. If you are using an array, one way is to sort it in $$O(n\log(n))$$ and then you can check whether an item exists using binary search in $$O(\log(n))$$. One other way is to use hash tables data structures like dictionaries in Python where you can answer such question in $$O(1)$$. Check Python Dictionaries or C++ Maps.
• No. $O(n\log n)$ is slower that what OP suggests. And a hash table still requires you to process all the input. – AstridNeu Sep 18 '19 at 21:20