what would be the run time of this function using master's theorem-CodePudding

    IN-TREE(p, k) 
    if p == NIL 
        return FALSE 
    else if p.key == KEY 
        return TRUE 
    else 
        return IN-TREE(p.left, k) or IN-TREE(p.right, k)

p points to a node in a complete linked binary tree and has each node p has a key called p.key, a pointer to its left subtree p.left, and a pointer to its right subtree p.right. An empty subtree is written as NIL.

What would be the run time of this function using master's theorem?

CodePudding user response：

It is clearly evident that in the worst-case scenario, you are going to look over all the nodes in the tree to match the node's key with KEY.

Therefore time complexity of this solution is O(n), where n is the number of nodes in the Tree.

CodePudding user response：

A complete tree of depth d has 2^d-1 nodes. So in the worst case (when the key is not found),

T(d) = C   T(d-1)   T(d-1).

If we rewrite in terms of the number of nodes,

T(N) = C   2 T((N-1)/2).

As the independent term is constant, the solution is linear in N.