When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)$. Can somebody explain it to me?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
For simplicity assume that the Merkle tree is a perfect binary tree. Let the number of data blocks is $n$ which are linked to the leaf nodes. Therefore the total number of tree nodes are $|nodes| = n + n/2+ \cdots +1$. If we assume that $n =2^k$ for simplicity than $$|nodes| = 1 + 2 + 2^2 + \cdots + 2^k = \frac{2^k-1}{2-1} = 2^k-1 = n-1.$$ In total, we have $n+ n -1 $ nodes, that is together with the data blocks. As a result the number of nodes are $\mathcal{O}(n)$.
In another approach, you can consider the height of the tree as the search complexity, $h = c \log n$ then the maximum number of a binary tree with $h$ is $2^h-1 = 2^{c \log n}-1 = n 2^c-1 \in \mathcal{O}(n)$. Adding the data block will not change the complexity.
Note: In a complete binary tree, if we say that the root is level 1 then the $i$-th level contains $2^{i-1}$ nodes. Each level will contain a double of the previous level.
answered Mar 21, 2020 at 14:39
-
$\begingroup$ Thank you, I got the point. According to this, for example certificate revocation list is also growing 1 + 2 + 3 +...n so on. In this way, its complexity O(N^2). Is it correct? $\endgroup$– jhdmMar 22, 2020 at 20:57
-
$\begingroup$ No. For $n$ data elements the depth is $\log n$. For the certificate, you can go up to $\log n$ and the neighbors, the makes around $2 \log n$ $\endgroup$– kelalakaMar 22, 2020 at 21:00
-
$\begingroup$ @ kelalaka Sorry I dont understand how its space complexity is logn.Just adding new ones to list like 1,2,3...n? $\endgroup$– jhdmMar 22, 2020 at 21:16
-
$\begingroup$ Do you know how one can go to the root of a leaf in a complete binary tree? One travel parent of the parent of .... then the root. In the query, you asked for a data element that is linked to a lead. Now you need the neighbors for the validation of the hashes to the root. Since one can reach the root in $\log n$ step then the number of elements need to be transferred can not pass $\mathcal{O}(\log n)$ $\endgroup$– kelalakaMar 22, 2020 at 21:21
-
1$\begingroup$ @ kelalaka I thought that I should be add 1+2+3..+n then o(n^2) but I misthinking. its size just n, it should be o(n). Thank you so much $\endgroup$– jhdmMar 22, 2020 at 21:54