What is the runtime to access an element from an array or hash table? How is it different from find or search?

Question

In a completely theoretic analysis to computing algorithm runtimes; If I want to include a line in my psuedo code that involves searching for a value in an array or a value of a hash table given a key, what should I assume the runtime of this operation to be? For example if I previously stored A[3] = 6 and the I call A[3] to retrieve 6 would the runtime of this operation be O(1)? Or would it be considered a search operation using some optimal search algorithm and be O(log n) where n is the number of elements in A?

Answer 1

Assuming we're talking about a vanilla integer-indexed array, stored in a single contiguous piece of memory, indexing into it is typically performed by a single addition, making the access constant time.

http://en.wikipedia.org/wiki/Array_data_structure#Efficiency

Likewise, hash tables typically provide constant-time access, though that constant is pretty much guaranteed to be larger than array indexing's constant, because hash tables are more complex and generally built on top of arrays. Reasonable hash functions alone require much more than a single add operation.

http://en.wikipedia.org/wiki/Hash_table#Performance_analysis