7.1 - Test Results

Sequential Data Results

N	`std::set`	`std::unordered_set`	`VectorSet`	`BST`	`AVL`	`HashSet`
1,000	0	0	7	6	0	0
10,000	9	5	289	498	8	10
100,000	61	31	25561	49908	59	51
1,000,000	388	153	TSTT	TSTT	375	256
10,000,000	4287	1337	TSTT	TSTT	4475	4219

Random Data Results

N	`std::set`	`std::unordered_set`	`VectorSet`	`BST`	`AVL`	`HashSet`
1,000	0	0	4	0	0	1
10,000	8	7	335	4	9	13
100,000	61	47	31170	49	70	60
1,000,000	688	364	TSTT	457	738	689
10,000,000	13382	5462	TSTT	11690	14483	7432

Big O - Observed Insertion

`std::set`	`std::unordered_set`	`VectorSet`	`BST`	`AVL`	`HashSet`
$l o g (n)$	$l o g (n)$	$n$	$n$ or $l o g (n)$ for random	$l o g (n)$	$l o g (n)$

Big O - Theoretical Insertion

	`std::set`	`std::unordered_set`	`VectorSet`	`BST`	`AVL`	`HashSet`
Average Case	$l o g (n)$	1	$n$	$n$ or $l o g (n)$ for random	$l o g (n)$	$l o g (n)$
Worst Case	$l o g (n)$	$l o g (n)$

Based on the times you recorded, what is the Big-Oh of insert for each of these six implementations of sets?

`std::set`	`std::unordered_set`	`VectorSet`	`BST`	`AVL`	`HashSet`
$l o g (n)$	$l o g (n)$	$n$	$n$ or $l o g (n)$ for random	$l o g (n)$	$l o g (n)$

Are these Big-Ohs what you expected them to be? Why or why not? Be sure to explore any surprises that you see in the data. You should compare the Big-Ohs to the theoretical Big-Ohs that you have learned about (in class, through quizzes, etc.). Are the implementations you created as efficient as they should be? If not, can you explain why?

Overall, the Big-Ohs seem to be pretty close to expected. My implementations of VectorSet and BST seem to be pretty slow, as I got two TSTTs for each. I am not sure why they are quite slow. The other implementations are quite zippy and match pretty well with what is expected.

How did the results change based on ordered data verses random data? Make sure you can explain the similarities and differences.

The only one that had a significant difference was the BST, which had a significant speed up with random data.