# Multiset-Trie Data Structure
## 4 Mathematical Analysis of the Structure
### Time Complexity of the Algorithms
#### 4.1.1 Mathematical Model  
We start with the basics of our mathematical model. Let \(\Sigma\) be an alphabet of cardinality \(\sigma\), such that \(\Sigma=\{1,2,\ldots,\sigma\}\). Define \(N\) to be the set of all possible multisets that can be inserted in a multiset-trie. Let \(n\) be the maximal degree of a node in a multiset-trie. Then, the maximal multiplicity of an element in a multiset is equal to \(n-1\). Thus, the number of multisets in a complete multiset-trie is \(|N|=n^{\sigma}\). Let \(M\) be a collection of multisets inserted into multiset-trie \(\mathcal{M}\). All the multisets in \(M\) are constructed from the alphabet \(\Sigma\) according to the parameters \(\sigma\) and \(n\). Hence, any multiset \(m\in M\), has at most \(\sigma\) distinct elements that are members of \(\Sigma\), and every distinct element in \(m\) has multiplicity strictly less than \(n\). Because a multiset does not distinguish different orderings, it is assumed, for simplicity, that all elements are ordered in ascending order. A multiset \(m\) is represented as \(\{1^{k_{1}},2^{k_{2}},\ldots,\sigma^{k_{\sigma}}\}\), where \(e^{k_{\sigma}}\) represents an element \(e\in\Sigma\) with multiplicity \(k_{\sigma}\). Denote the nodes of multiset-trie on all levels but on \(\sigma+1\) as _internal_ and nodes on the leaf level as _leaf_ nodes. Observe that every internal non-root node has a degree of at least 1. Indeed, the insertion of a multiset requires the construction of a path of length \(\sigma+1\), meaning that if an internal node exists in a multiset-trie, it must have a degree of at least 1. It also follows that the height of a multiset-trie is always \(\sigma+1\) as soon as at least one multiset is inserted into the data structure. Our model assumes that all the inserted multisets are chosen with the same probability, meaning that for some \(p\in(0,1)\), the following holds:  
\[P(m\in M)=p,\quad\forall\ m\in N.\]  
Let \(\xi_{1},\xi_{2},\ldots,\xi_{\sigma+1}\) be random variables such that \(\xi_{i}\) represents the number of nodes in a multiset-trie on the \(i\)-th level. For every node \(j\) on \(i\)-th level, we assign a random variable \(\xi_{ij}\) to be the number of its children, such that \(j\in[1,\xi_{i}]\). Then, for every \(i\in[1,\sigma]\), the following holds:  
\[\xi_{i+1}=\sum_{j=1}^{\xi_{i}}\xi_{ij}, \tag{1}\]  
where \(\xi_{1}=1\). It is easy to see that the variable \(\xi_{i+1}\) can have values in the interval \([\xi_{i},n^{i}]\) and the value of the variable \(\xi_{ij}\) is within the interval \([1,n]\). Without conditioning on the existence of any node in multiset-trie, it is easy to describe the probability of the existence of any individual node. Lemma 1: _Any potential node on a fixed level \(i\), where \(i\in\{1,2,\ldots,\sigma+1\}\) exists, with probability_  
\[p_{i}=1-(1-p)^{n^{\sigma+1-i}}. \tag{2}\]  
Proof: Let \(v\) be an arbitrary node in a multiset-trie on an arbitrary level \(i\). Consider the subtree with the root \(v\) and call it the \(v\)-subtree. Since the height of the multiset-trie is \(\sigma+1\), we can calculate the height of the \(v\)-subtree. Taking into account that the root node has height \(1\), the height of the \(v\)-subtree is  
\[h_{v}=\sigma+1-i.\]  
A node in a multiset-trie exists if at least one node exists on the leaf level of its subtree, i.e., a node on the level \(\sigma+1\) that belongs to \(v\)-subtree. The possible number of nodes on the leaf level of \(v\)-subtree can be easily calculated knowing its height. It is equal to  
\[n^{\sigma+1-i}.\]  
A node at level \(\sigma+1\) exists with probability \(p\), where \(p=P(m\in M)\). Thus, the probability that there are no nodes on the leaf level in \(v\)-subtree is  
\[(1-p)^{n^{\sigma+1-i}}.\]  
The claim follows by taking the complement probability of the above result.