-2
$\begingroup$

A program must construct and then use a set $S$ of 1000 integers.

/* part 1 */

S = empty
for i from 1 to 10000 {

...

x = ...

add x to S

}

/* part 2 */

for j from 1 to 100000 {
...
y = ....
test if y belongs to S
...
}

To represent S you have the choice between

  • a double-linked list

  • a balanced binary search tree

  • an open hash table size 100

  • an open hash table size 5000


  1. What will be the most efficient solution for Part 1 of the program?
  2. What will be the most efficient solution for Part 2 of the program?
  3. What will be the most efficient solution overall?
$\endgroup$
0
$\begingroup$

All solutions are equivalent, as far as asymptotic complexity is concerned, since they all require $\Theta(1)$ time.

$\endgroup$
0
$\begingroup$

The most efficient would be a hash table with say 15,000 slots or one that dynamically changes its size. The most efficient solution overall is to use whatever your development environment provides.

Note that you don’t say what x is. For a hash table, you need the ability to calculate hash values and check for equality. For a search tree, you need an ordering (<, =, >) of the values. For a linked list, you need plenty of time :-)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.