CODEWITHSUNDEEP
data-structureshashhashtable
xyz
xyz

Reputation: 2170

Hashing analysis in hashtable

The search time for a hash value is O(1+alpha) , where 

 alpha = number of elements/size of table

I don't understand why the 1 is added?

The expected number elements examined is 

(1/n  summation of i=1 to n (1+(i-1/m)))

I don't understand this too.How it is derived?

(I know how to solve the above expression , but I want to understand how it has been lead to this expression..)

EDIT : n is number of elements present and m is the number of slots or the size of the table

Upvotes: 0

Views: 73

Answers (1)

armel
armel

Reputation: 2580

I don't understand why the 1 is added?

The O(1) is there to tell that even if there is no element in a bucket or the hash table at all, you'll have to compute the key hash value and thus it won't be instantaneous.

Your second part needs precisions. See my comments.

EDIT: Your second portion is there for "amortized analysis", the idea is to consider each insertion in fact in a set of n insertions in an initially empty hash table, each lookup would take O(1) hashing plus O(i-1/m) searching the bucket content considering each bucket is evenly filled with respect to previous elements. The resolution of the sum actually gives the O(1+alpha) amortized time.

Upvotes: 1

Related Questions