Timeline for How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 29, 2016 at 0:43 | comment | added | Charlie Parker | sorry if this is super easy/obvious to you. But how does that assumption make this possible? If you could write some details for this I would be really grateful. | |
| Feb 27, 2016 at 14:59 | comment | added | Raphael | See the two numbered list items. The simple uniform hashing assumption allows us to ignore the actual keys. | |
| Feb 26, 2016 at 22:47 | comment | added | Charlie Parker | There are two sources of randomness, the keys and the lengths of the table. The lengths of the chains is clearly dependent on how the hash function spreads elements out randomly. However, the part that isn't 100% clear from your answer is how you took care of the distribution of which keys we searched for. If $$E[T] = \sum^{n}_{i=1} E_{t \sim Pr[T]} [T_{h(k)}] Pr[Key = k]$$ is the expected time to search for any key, then, why can't you just simply conclude $E_{t \sim Pr[T]} [T_{h(k)}] \leq E_{n \sim Pr[N]} [n_{h(k)}] = \frac{n}{m}$ and just call everything done by pluging it in to $E[T] $? | |
| Feb 16, 2016 at 11:44 | history | edited | Raphael | CC BY-SA 3.0 |
added 1721 characters in body
|
| Feb 16, 2016 at 11:14 | history | answered | Raphael | CC BY-SA 3.0 |