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

Answer 2

Retrieving a value from a hash is linear time in the worst case (meaning the case when every key hashes to the same value), but its average case is constant time. If you're dealing with a real-time system then you need to treat it as though it were O(n), but generally you can treat it as though it were O(1).

Answer 3

if A[3] = 6; and you want to get A[3] then its a O(1) step because array allocates memory for each element. Lets say A is a int array and location of 0th element is x then
location of 1st element is x+4 (considering int to be 4 bytes)
location of 2nd element is x+8
location of 3rd element is x+12 ... Like wise all element.
so location of ith element is x+4*i;
Hence java directly go to the address and fetch the corresponding element in constant time.