0
$\begingroup$

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.

$\endgroup$

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 2
    $\begingroup$ 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. $\endgroup$ – AstridNeu Sep 18 at 21:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Marcelo Fornet Oct 18 at 5:33
  • $\begingroup$ 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)? $\endgroup$ – Steven Oct 18 at 17:37
1
$\begingroup$

If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do.

If you want to carry out multiple tests (but you do not know all the test items in advance) then it is worth the initial overhead of sorting the list, creating a hash table, or creating a search tree.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No. $O(n\log n)$ is slower that what OP suggests. And a hash table still requires you to process all the input. $\endgroup$ – AstridNeu Sep 18 at 21:20
  • $\begingroup$ Hash tables will not guarantee O(1) worst case lookup time without special care. $\endgroup$ – Juho Oct 18 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.