# Calculating efficiency?

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?

## 2 Answers

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

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 :-)