CODEWITHSUNDEEP
algorithmhashhashtableprobabilityhashcode
user2149873
user2149873

Reputation: 163

hash table load factor a and n slots, open adressing for collisions

I was at the high freq Trading interview they asked me all mathematical side of data structures one question was: load factor a=1-1/(sqrt(n)logn), what is the time for unsuccessful search? state the answer using only 'n'

Upvotes: 0

Views: 483

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134125

The term 1-1/(sqrt(n)*log(n)) approaches 1.0 as n increases. When n==10, the value is 0.9048. When n==1000000, the value is 0.9999. (I'm using log base 2.)

With a full hash table (which is what a load factor of 1.0 means) and open addressing, you'd have to examine every item. So the time for an unsuccessful search would be O(n).

Upvotes: 1

Related Questions