# Multiset-Trie Data Structure
## 4 Mathematical Analysis of the Structure
### Time Complexity of the Algorithms
#### 4.1.3 SubmsetExistence and SupermsetExistence  
We start the analysis of the functions submsetExistence and supermsetExistence with an observation. Our theoretical model assumes that all the multisets are inserted into multiset-trie at random. It was already concluded that the probability distribution function \(P(m\in M)\) has an impact on the size of multiset-trie \(\mathcal{M}\). Moreover, this distribution influences the performance of the functions submsetExistence and supermsetExistence even more. For a real-world model, such that \(P(m\in M)\
eq const\), the performance of the search algorithms directly depends on the number of nodes on every level \(\xi_{i}\). When the search functions check if a multiset is in multiset-trie, the complete path that corresponds to this multiset is checked. Knowing this fact, the search can be optimized during the construction of a multiset-trie. Recall that a multiset-trie is defined on parameters \(n\), \(\Sigma\), \(\sigma=|\Sigma|\), and \(\phi\). Let the frequency of an element \(e\) in a multiset \(m\) be the multiplicity of \(e\) in \(m\), denoted by \(mult_{m}(e)\). Then, the frequency of an element \(e\) can be defined as a sum \(\sum_{m\in M}mult_{m}(e)\). According to the frequencies of elements in \(\Sigma\), the performance of the multiset-trie can be optimized by the mapping \(\phi:\Sigma\to I\). Indeed, the ordering of elements by their frequencies has an influence on the performance. The frequency of an element \(e\in\Sigma\) affects the distribution of \(\xi_{\phi(e)}\) as follows. The larger the frequency of \(e\), the larger the number of nodes on the \(\phi(e)\) level. Thus, if the number of nodes on lower levels is greater than on higher levels, then the search functions will discard complete paths that do not satisfy the query faster. Hence, the closest match will be found faster. Let us now switch back to our mathematical model and note that the influence of the mapping function \(\phi\) in our model has an inessential impact on the performance, because all the multisets are equally likely, and the whole domain \(N\) is used for sampling multisets. Consider both functions submsetExistence and supermsetExistence. Whenever the result is _false_, i.e., no multiset in \(M\) is a sub-multiset or super-multiset of an input multiset \(m\), both functions in the worst case visit all the nodes in \(\mathcal{M}\) but the nodes on the leaf level. Of course, such a case would be very rare, assuming a random input model, but it can be constructed as follows. Consider the function submsetExistence. Then, given an input multiset \(m=\{1^{k_{1}},2^{k_{2}},\ldots,\sigma^{k_{\sigma}}\}\), the collection of inserted multisets \(M\) must be equal to \(M=\{x\in M:k_{x,\sigma}>k_{m,\sigma}\}\). Analogically, for the function supermsetExistence with an input multiset \(m=\{1^{k_{1}},2^{k_{2}},\ldots,\sigma^{k_{\sigma}}\}\), the collection of inserted multisets \(M\) must be equal to \(M=\{x\in M:k_{x,\sigma}<k_{m,\sigma}\}\). Thus, the worst-case running time complexity of the functions submsetExistence and supermsetExistence is \(O(|\mathcal{M}|-|M|)\). According to Theorem 2, this value is  
\[O(\sum_{i=1}^{\sigma}n^{i-1}\frac{1-(1-p)^{n^{\sigma+1-i}}}{1-(1-p)^{n^{\sigma }}}).\]  
According to Theorem 1, the worst-case running time given an input multiset \(m\) for the function submsetExistence is  
\[O(\sum_{i=1}^{\sigma}\alpha_{i-1}\frac{1-(1-p)^{\alpha_{i-1}}}{1-(1-p)^{\alpha _{\sigma}}})\]  
and for the function supermsetExistence is  
\[O(\sum_{i=1}^{\sigma}\beta_{i-1}\frac{1-(1-p)^{\beta_{i-1}}}{1-(1-p)^{\beta_{ \sigma}}}).\]Note that the summation goes only up to \(\sigma\) and not up to \(\sigma+1\) as in Theorem 2 or in Theorem 1. As for the case wherein the outcome of the functions submsetExistence and supermsetExistence is _true_, one has to guarantee the termination of the algorithm at some node on the leaf level. The worst-case scenario can be constructed in the same way as for the _false_ outcome but with two more multisets in \(M\).