3
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
12
  • $\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$
    – jhdm
    Mar 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$
    – kelalaka
    Mar 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$
    – jhdm
    Mar 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$
    – kelalaka
    Mar 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$
    – jhdm
    Mar 22, 2020 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.