0
$\begingroup$

I have a simple recursive function that compares two merkle trees and accumulates the differences in the leaf nodes. However, I am unable to measure the time complexity of it. Specifically, I would like to see how does it compare against comparing two Hashtables or two BSTs. A group of leaves is a row in this case and they share a rowid. In the code below I am just accumulating the differences at the leaf level.

def diff_helper(node1: MNode, node2: MNode, diff: List[Difference]):
    if not node1 and not node2:
        return
    elif node1.rowid==node2.rowid and node1.signature==node2.signature and node1.nodetype==NodeType.Row and node2.nodetype==NodeType.Row:
        return
    elif node1.rowid==node2.rowid and node1.signature!=node2.signature and node1.nodetype==NodeType.Row and node2.nodetype==NodeType.Row:
        diff_helper(node1.left, node2.left, diff)
        diff_helper(node1.right, node2.right, diff)
    elif node1.rowid==node2.rowid and node1.signature!=node2.signature and node1.nodetype==NodeType.Leaf and node2.nodetype==NodeType.Leaf:
        diff.append(Difference(node1.rowid, node1.column, node1.value, node2.value))
    else:
        diff_helper(node1.left, node2.left, diff)
        diff_helper(node1.right, node2.right, diff)

Time complexity:

  1. On the best case, I see that this is a constant operation since the root hashes of both trees would be the same.
  2. On the worst case, the number of comparisons is the total number of all leaf nodes.

Question:

Assuming the above time complexity, it doesn't seem to fare any better than comparing two Hashtables where each key is a rowid and the values being leaves. I understand that with Hashtable, once you find the values of the rowid, you'll need to do a linear comparison of each leaf as compared to O(logm), m being the number of leaves under each row. How would you represent that in Big O terms?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.