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?


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.

  • $\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 '20 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 '20 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 '20 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 '20 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 '20 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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