Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$ for $N = 2$ is $\Omega(\sqrt{n})$, where $n$ is the total number of keys in the table (as a last resort, at least $\Omega(\log n)$)?

  • 1
    $\begingroup$ Where do the $a_i$'s lie, what is the domain of the hash function? Where does the public key come in? Is the hash chosen at random? Those details are crucial to being able to give a meaningful answer. $\endgroup$
    – Ariel
    Dec 1 '20 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.