# FASTSET: A Fast Data Structure for the Representation of Sets of Integers
## 5 Space Complexity and Limitations  
The data structure we have described may not be appropriate when the universe of all possible values is very large, especially if the amount of available memory is an issue. Indeed, the memory requirement is \(\Theta(N)\) and this can be prohibitive (e.g., when \(N\) is a large power of 2 such as \(N\geq 2^{32}\)). In this case, even if the memory is available, it is hard to assume that the allocation of such a chunk of memory is an \(O(1)\) operation.  
The same problem, however, would be true of other data structures which require \(\Theta(N)\) memory, such as the bitmaps and the optimal hashtables. Clearly, when the size of the set \(S\subset\{0,\ldots,N-1\}\) tends to become as large as \(N\), all the possible data structures would incur in the same memory problem (indeed, in this case our structure would be optimal as far as memory consumption, since it would be linear in the size of the set). When, on the other hand \(|S|\ll N\) then data structures based on dynamic allocation of memory (such as linked lists and AVL trees) are better as far as memory consumption than FASTSETs. We remark, however, that the case of an exponentially large \(N\) is a rare  
\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Nodes** & **Edges** & **FASTSET** & **BitSet** & **TreeSet** & **HashSet** \\ \hline \multirow{3}{*}{1000} & 500 & 40 & 53 (132\%) & 109 (272\%) & 556 (1390\%) \\  & 2500 & 112 & 278 (248\%) & 543 (485\%) & 1612 (1439\%) \\  & 5000 & 150 & 515 (343\%) & 1256 (837\%) & 2387 (1591\%) \\ \hline \multirow{3}{*}{3000} & 4500 & 619 & 1565 (253\%) & 3497 (565\%) & 41556 (6713\%) \\  & 22500 & 2603 & 8024 (308\%) & 22219 (854\%) & 76372 (2934\%) \\  & 45000 & 5410 & 22131 (409\%) & 54704 (1011\%) & 105664 (1953\%) \\ \hline \multirow{3}{*}{5000} & 12500 & 2412 & 9344 (387\%) & 17719 (735\%) & 265533 (11008\%) \\  & 62500 & 14993 & 53829 (359\%) & 141739 (945\%) & 510208 (3403\%) \\ \cline{1-1}  & 125000 & 37494 & 126521 (337\%) & 379501 (1012\%) & 754031 (2011\%) \\ \hline \multicolumn{2}{l}{avg. \% vs. FASTSET} & \multicolumn{2}{c}{308\%} & \multicolumn{2}{c}{746\%} & \multicolumn{2}{c}{3605\%} \\ \hline \hline \end{tabular}
\end{table}
Table 4: Time comparison (in milliseconds) for some set implementation found in the java.util package of the Java standard library vs. FASTSET in solving the max cut problem using a greedy algorithm (average time over 5 random graph instances, the same for any set type). The shown percentages are relative to the FASTSET time.  
\begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Nodes** & **Edges** & **FASTSET** & **BitSet** & **TreeSet** & **HashSet** \\ \hline \multirow{3}{*}{1000} & 500 & 31 & 68 (219\%) & 81 (261\%) & 90 (290\%) \\  & 2500 & 40 & 93 (232\%) & 109 (272\%) & 115 (287\%) \\  & 5000 & 49 & 109 (222\%) & 131 (267\%) & 125 (255\%) \\ \hline \multirow{3}{*}{3000} & 4500 & 253 & 646 (255\%) & 790 (312\%) & 1031 (408\%) \\  & 22500 & 431 & 1050 (244\%) & 1322 (307\%) & 1606 (373\%) \\  & 45000 & 487 & 1137 (233\%) & 1574 (323\%) & 1765 (362\%) \\ \hline \multirow{3}{*}{5000} & 12500 & 1025 & 2237 (218\%) & 2950 (288\%) & 3937 (384\%) \\  & 62500 & 1547 & 3109 (201\%) & 4575 (296\%) & 5974 (386\%) \\ \cline{1-1}  & 125000 & 1759 & 3253 (185\%) & 4896 (278\%) & 6581 (374\%) \\ \hline avg. \% vs. FASTSET & \multicolumn{2}{c}{223\%} & \multicolumn{2}{c}{289\%} & \multicolumn{2}{c}{347\%} \\ \hline \hline \end{tabular}
\end{table}
Table 3: Time comparison (in milliseconds) for some set implementation found in the java.util package of the Java standard library vs. FASTSET in solving the vertex cover problem using a greedy algorithm (average time over 5 random graph instances, the same for any set type). The shown percentages are relative to the FASTSET time.  
situation, since most of the times the integers that we deal with in our sets are indices, identifying the elements of a size-\(N\) array representing a problem instance.