March 13, 2013
We got in a bit of a debate yesterday in the office over the implementation of associative containers, which I thought was pretty fun. We made up the big chart of complexity results you see below.
nomenclature: $S$, $S_1$, and $S_2$ are subsets of $\Omega$. Denote an element by $e\in\Omega$. $n$,$n_1$,$n_2$,$N$ are the sizes of the set $S$, $S_1$, $S_2$, and $\Omega$, respectively, and $n_1 \geq n_2$. Complexity Operation\Approach Hash Table Hash Tree Binary List Entry List (sorted) Entry List (unsorted) $e \in S $ $O(1) $ $O(log(n)) $ $O(1) $ $O(log(n)) $ $O(n) $ $S_1 \cup S_2 $ $O(n_1+n_2) $ $O(n_1+n_2) $ $O(N) $ $O(n_1+n_2) $ $O(n_1n_2) $ $S_1 \cap S_2 $ $O(n_1) $ $O(log(n_1)n_2)$ $O(N) $ $O(n_2) $ $O(n_1n_2) $ space complexity $O(n) $ $O(n) $ $O(N)$ bits.