# Merkle Tree space complexity

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?

## 1 Answer

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.

• 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? – jhdm Mar 22 at 20:57
• 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$ – kelalaka Mar 22 at 21:00
• @ kelalaka Sorry I dont understand how its space complexity is logn.Just adding new ones to list like 1,2,3...n? – jhdm Mar 22 at 21:16
• 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)$ – kelalaka Mar 22 at 21:21
• @ 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 – jhdm Mar 22 at 21:54