0

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

Improve this question
2
  • please specify during which operation "elements [are] examined"? during a single lookup? what are m and n in your expression? n is probably the total number of elements but m ?
    – armel
    Commented Jul 10, 2014 at 8:53
  • @armel thanks .. I have edited the question and yes during a single search operation and n is the number of elements present the table
    – xyz
    Commented Jul 10, 2014 at 9:06

1 Answer 1

Reset to default
1
+50

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.

Improve this answer
3
  • So it means to search that particular element, a key hash value for the same is calculated over a constant time O(1)..Am I correct?
    – xyz
    Commented Jul 10, 2014 at 9:11
  • 1
    O(1) here means that it is independent from the number of elements and the size of the hash table. It depends of course of the key complexity. Computing a hash key for an integer might be trivial and be constant time so O(1), while it may be O(string size) for strings and so on.
    – armel
    Commented Jul 10, 2014 at 9:20
  • OK got it thanks..and information about second part is relevant?anything else required from my end?
    – xyz
    Commented Jul 10, 2014 at 9:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.