CODEWITHSUNDEEP
algorithmbinary-treetime-complexityrecurrence
user4791206
user4791206

Reputation:

Recurrence relation for given algorithm?

int print4Subtree(struct Node *root) {
    if (root == NULL)
      return 0;
    int l =  print4Subtree(root->left);
    int r =   print4Subtree(root->right);
    if ((l + r + 1) == 4)
       printf("%d ", root->data);
    return (l + r + 1); }

This algorithm/code finds number of subtrees having exactly 4 nodes in binary tree , it's works in bottom-up manner . I know the time complexity of this code would be O(n) , and space complexity is O(log n) , since it's using recursion.

What will be recurrence relation for the code ?

I try to draw T(n) = 2T(n-1)+1 , which is obviously wrong !

Upvotes: 1

Views: 1842

Answers (1)

Linus
Linus

Reputation: 894

You can only talk about recurrence relations in terms of n alone in cases where you know more about the structure of the tree, for instance:

Case 1: Every node has only one child meaning T(n) = T(0) + T(n-1) + k.
Case 2: Subtrees at any level are balanced so that T(n) = 2 T((n-1)/2) + k.

Both of these will result in O(n), but these two cases are only a very select minority of possible trees. For a more universal approach you have to use a formula like T(n) = T(a) + T(b), where a and b are an arbitrary division into sub-problems resulting from the structure of your tree. You can still establish results from this kind of formula using strong induction.

The following is the exact formula and approach I would use:
T(n) = nk + mnc, where mn ≤ n + 1. (Note: I am using k for overhead of recursive steps and c for overhead of base/null steps).

Base case (n=0):
For a null node T(0) = c so T(n) = kn + mnc ,
where mn = 1 ≤ n+1 = 1.
Inductive step (T(x) = xk + mxc for all x < n):
The sub_tree of size n has two sub-trees of sizes a and b (a or b may be 0) such that n = a + b + 1.
T(n) = T(a) + T(b) + k = ak + mac + bk + mbc + k = (a+b+1)k + (ma+mb)c = nk + mnc ,
where mn = ma + mb ≤ a + 1 + b + 1 = n + 1.

The reason for using mn is merely a formality to make the proof smoother, as the exact number of null cases is what is actually affected by the structure of tree (in the former case 2, it is log n). So T(n) is at best O(n) because of the nk term, and can be no worst than O(n) because of the bound on mnc.

Upvotes: 1

Related Questions