# DenseZDD: A Compact and Fast Index for Families of Sets +
## 5 Complexity Analysis  
Let the length of balanced parentheses sequence \(U\) be \(2u\), where \(u\) is the number of ZDD nodes with dummy nodes. When a ZDD has \(m\) nodes and the number of items is \(n\), \(u\) is \(mn\) in the worst case. Here, we show how to compress the BP sequence \(U\).  
We would like to decrease the space used by DenseZDD. However, we added extra data, dummy nodes, to the given ZDD. We want to bound the memory usage caused by dummy nodes. From the pseudo-code in Algorithm 2, we observe that the BP sequence \(U\) consists of at most \(2m\) runs of identical symbols. To see this, consider the substring of \(U\) between the positions for two real nodes. There is a run consisting of consecutive '\(\prime\)' followed by a run consisting of consecutive '\((\prime\)' in the substring. We compress \(U\) by using some integer encoding scheme such as the delta-code or the gamma-code [15]. An integer \(x>0\) can be encoded in \(\mathcal{O}(\log x)\) bits. Since the maximum length of a run is \(n\), \(U\) can be encoded in \(\mathcal{O}(m\log n)\) bits. The range min-max tree of \(U\) has \(2m/\log m\) leaves. Each leaf of the tree corresponds to a substring of \(U\) that contains \(\log m\) runs. Then, any tree operation can be done in \(\mathcal{O}(\log m)\) time. The range min-max tree is stored in \(\mathcal{O}(m(\log n+\log m)/\log m)\) bits.  
We also compress the dummy node vector \(B_{D}\). Since its length is \(2u\leq 2 mn\) and there are only \(m\) ones, it can be compressed in \(m(2+\log m)+o(u)\) bits by FID. The operations \(select_{1}\) and \(rank_{1}\) take constant time. We can reduce the term \(o(u)\) to \(o(m)\) by using a sparse array [16]. Then, the operation \(select_{1}\) is done in constant time, while \(rank_{1}\) takes \(\mathcal{O}(\log m)\) time. We call the DenseZDD whose zero-edge tree and dummy node vector are compressed dummy-compressed DenseZDD.  
From the discussion in the section, we can prove Theorems 1 and 2.  
Proof of Theorem 1.: From the above discussion, the BP \(U\) of the zero-edge tree costs \(2u=\mathcal{O}(mn)\) bits, where \(u\) is the number of real nodes and dummy nodes. The one-child array needs \(m\log m\) bits for 1-children and \(m\) bits for \(\emptyset\)-flags. Using FID, the dummy node vector is stored in \(m(2+\log m)+o(u)\) bits. Therefore, the DenseZDD can be stored in \(2u+3m+2m\log m+o(u)\) bits and the primitive operations except \(getnode\) are done in constant time because the \(rank_{1}\), \(select_{1}\), and any tree operations take constant time by Proposition 1.  
Proof of Theorem 2.: When we compress \(U\), it can be stored in \(\mathcal{O}(m\log n)\) bits and the min-max tree is stored in \(\mathcal{O}(m(\log n+\log m)/\log m)\) bits. The dummy node vector can be compressed in \(m(2+\log m)+o(m)\) bits by FID with sparse array. The time of any tree operations and the \(rank_{1}\) operation is \(\mathcal{O}(\log m)\). Therefore, the DenseZDD can be stored in \(\mathcal{O}(m(\log m+\log n))\) bits and the primitive operations except for \(getnode\) take \(\mathcal{O}(\log m)\) time because all of them use tree operations on \(U\) or \(rank_{1}\) on \(M\).