knowing only the number of keys, n, how can you create a data structure of some sort that satisfies the following:

  1. initialization takes O(n) time
  2. after being initialized, you can insert and search keys and the probability that these actions take O(1) time is higher than 0.5.

how can you extend the algorithm so that the probability for (2) is higher than 0.75?

and in general, how can you extend it so that the probability is higher than $1-0.5^c$ for some natural c, and the time complexity is $O(n^2)$?

thank you!

  • $\begingroup$ What precisely do you mean by "the probability that these actions take $O(1)$ time"? $\endgroup$ – Robert Israel Jun 4 at 12:00

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.