0

Is there any search algorithm with time complexity O(1)?

Search Algorithm = Finding an element x from n elements.

Improve this question
9
  • Define "search algorithm" Commented Jan 24, 2013 at 16:46
  • But hashtable' worse look up is not O(1). Commented Jan 24, 2013 at 16:48
  • Algorithm for finding an integer x from a given n integers would be a search algorithm. Commented Jan 24, 2013 at 16:51
  • Search algorithm on what input? An unsorted array? Commented Jan 24, 2013 at 16:52
  • 1
    @tanvi: If the input is just an array and you count pre-processing time (that might be required by the search algorithm), then no, such algorithm does not exist. Commented Jan 24, 2013 at 16:57

2 Answers 2

Reset to default
1

Although I would be surprised if a search algorithm that was deterministically O(1) existed, the good news is that you can get lookup that is arbitrarily close to 100% accurate with O(1) add and lookup operations using a bloom filter. (http://en.wikipedia.org/wiki/Bloom_filter)

Similarly, a variety of techniques exist for those sets with finite sizes (http://en.wikipedia.org/wiki/Perfect_hash_function) although if those set sizes are very large problems arise in practice

However, to the general case, the answer is, to the best of my knowledge, no. And certainly not in any practical applications.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Yes, create a huge array, so that each possible value has one slot. Storing values and looking up values has time complexity O(1).

Edit:

If the initialisation time is counted also, then it's absolutely impossible to make an O(1) search algorithm. Searching an array without preprocessing can never be better than O(n), and there is no way to preprocess n items in O(1).

Improve this answer

3 Comments

Preparing your array (given a bunch of numbers to search in) would take O(n) time. I don't know whether this time counts as part of search time, considering how vague the question is.
@AndreyT: Naturally, storing n items anywhere can't take O(1).
Exactly. Which is why the question needs to be clarified. The clarifications provided by the OP so far (preprocesisng time is counted as part of the search time) naturally suggest that the O(1) algorithm is completely out of question.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.