You are not logged in. Please login at www.codechef.com to post your questions!

×

hash table search expected time

why In a hash table in which collisions are resolved by chaining an unsuccessful search and successful search both have same time complexity o(1+@). where @ is a load factor. reply soon

asked 08 Jul '13, 09:46

whiteknight321's gravatar image

0★whiteknight321
26689
accept rate: 0%


Unsuccessful search
O(1) to reach array location, O(@) to traverse the list or to reach the end of the list. (Please note We must reach the end of the list then only we can say that the element was not in the table),
so T(n) = 1+@ where @ = n/m, number of elements/ number of array locations.

Successful search
Assume that new element is inserted at the end of the linked list. Upon insertion of the ith element, the expected length of list is (i-1)/m.
In case of successful search, the expected no. of elements examined is 1 more.
So the time need T(n) = 1/n(∑1<=i<=n(1 + (i-1)/m)
= 1 + n/2m -1/2m
= 1 + @/2 -1/2m = O(1+@)
Comment if you don't get any point of my answer :)

link

answered 09 Jul '13, 03:32

v_akshay's gravatar image

4★v_akshay
1.2k91625
accept rate: 13%

edited 09 Jul '13, 03:35

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,475
×1,664

question asked: 08 Jul '13, 09:46

question was seen: 1,681 times

last updated: 09 Jul '13, 03:35