# 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 = ...

}

/* part 2 */

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


To represent S you have the choice between

• 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?

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