4

I am currently taking a university course in data structures, and this topic has been bothering me for a while now (this is not a homework assignment, just a purely theoretical question).

Let's assume you want to implement a dictionary. The dictionary should, of course, have a search function, accepting a key and returning a value.

Right now, I can only imagine 2 very general methods of implementing such a thing:

  • Using some kind of search tree, which would (always?) give an O(log n) worst case running time for finding the value by the key, or,
  • Hashing the key, which essentially returns a natural number which corresponds to an index in an array of values, giving an O(1) worst case running time.

Is O(1) worst case running time possible for a search function, without the use of arrays?

Is random access available only through the use of arrays?
Is it possible through the use of a pointer-based data structure (such as linked lists, search trees, etc.)?

Is it possible when making some specific assumptions, for example, the keys being in some order?

In other words, can you think of an implementation (if one is possible) for the search function and the dictionary that will receive any key in the dictionary and return its value in O(1) time, without using arrays for random access?

Improve this question
5
  • 1
    A hashtable is only O(1) in the worst case if you have perfect hashing. In practice, a hashtable is O(1) in the average case and usually O(n) in the worst case. Commented Apr 15, 2011 at 2:11
  • Interesting insight. I am not very familiar with how hashtables are implemented, aren't they generally implemented like the second method I've suggested? Commented Apr 15, 2011 at 2:14
  • 2
    Yes, but in real-world use cases you need to take hash collisions into account. Wikipedia has a simple overview to get you started. Commented Apr 15, 2011 at 2:16
  • Accounting for hash collisions means that each table entry will potentially hold multiple values, so it has to have an array. Depending on how strictly you interpret the "without arrays" requirement, that could mean that a hash table solution wouldn't be allowed for this question. Commented Apr 15, 2011 at 2:48
  • @Sherm: The table entries could have linked lists instead, so to be more specific, "without arrays" means without arrays that could be used like the second method in the question - preventing random access with arrays. Commented Apr 15, 2011 at 2:54

3 Answers 3

Reset to default
3

Here's another answer I made on that general subject. Essentially, algorithms reach their results by processing a certain number of bits of information. The length of time they take depends on how quickly they can do that.

A decision point having only 2 branches cannot process more than 1 bit of information. However, a decision point having n branches can process up to log(n) bits (base 2).

The only mechanism I'm aware of, in computers, that can process more than 1 bit of information, in a single operation, is indexing, whether it is indexing an array or executing a jump table (which is indexing an array).

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

Comments

3

It is not the use of an array that makes the lookup O(1), it's the fact that the lookup time is not dependent upon the size of the data storage. Hence any method that accesses data directly, without a search proportional in some way to the data sotrage size, would be O(1).

Improve this answer

13 Comments

This is true, for example, when accessing the i-th item in an array, or finding the minimum/maximum of some heaps/trees. I was wondering if it's possible for collections containing N elements.
@GeReV, I'm not quite sure what you're asking. An array has N elements.
I'm asking if there are, for example, some implementation of a search tree, a heap, etc. which doesn't use arrays as the underlying implementation but still retains O(1) search running times.
@GeReV, a tree by its nature has a root and branches that, depending upon how the tree is balanced, generally expand in size exponentially from the root. Hence, if we access a tree through the root, we will always have θ(log n) average run time. This is simply because the number of nodes visted is proportional to log n. So the answer is no, there are no O(1) tree implementations.
I'll try to explain my question a bit differently. The question is not specifically about trees, vectors, and so on. I am claiming that the only way to access a random item in memory is only possible through arrays (that is, a predictable memory address), and asking if that claim is true. If it's not true, could there possibly be some elaborate data structure that can access any of its elements without being dependent on the amount of elements, without translating the key into a memory address, like hashtables do?
|
1

you could have a hash implemented with a trie tree. The complexity is O(max(length(string))), if you have strings of limited size, then you could say it runs in O(1), it doesn't depend on the number of strings you have in the structure. http://en.wikipedia.org/wiki/Trie

Improve this answer

2 Comments

Yes but the minimum key size is still proportional to log n. So as n increases, so does the key. Hence this is still a O(log n) structure.
@ThomasMcLeod, While you are right in theory, this is basically a B-Tree just like a database. With a small amount of hand-waving you can consider it linear time lookup. For instance, if we allow the "string" to have the entire range of values for a byte, then with a length of 5 you have over a trillion possible values. While it's technically O(log n), in reality n is so small you can consider it constant.

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.