CODEWITHSUNDEEP
algorithmperformancedata-structuresgraphbig-o
Basir Doost
Basir Doost

Reputation: 21

Running time of algorithm with arbitrary sized recursive calls

I have written the following algorithm that given a node x in a Binary Search Tree T, will set the field s for all nodes in the subtree rooted at x, such that for each node, s will be the sum of all odd keys in the subtree rooted in that node.

OddNodeSetter(T, x):
    if (T.x == NIL):
        return 0;
    if (T.x.key mod 2 == 1):
        T.x.s = T.x.key + OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)
    else:
        T.x.s = OddNodeSetter(T, x.left) + OddNodeSetter(T, x.right)

I've thought of using the master theorem for this, with the recurrence 

T(n) = T(k) + T(n-k-1) + 1 for 1 <= k < n

however since the size of the two recursive calls could vary depending on k and n-k-1 (i.e. the number of nodes in the left and right subtree of x), I can't quite figure out how to solve this recurrence though. For example in case the number of nodes in the left and right subtree of x are equal, we can express the recurrence in the form

T(n) = 2T(n/2) + 1

which can be solved easily, but that doesn't prove the running time in all cases.

Is it possible to prove this algorithm runs in O(n) with the master theorem, and if not what other way is there to do this?

Upvotes: 2

Views: 56

Answers (2)

user1196549
user1196549

Reputation:

The algorithm visits every node in the tree exactly once, hence O(N).

Update:

And obviously, a visit takes constant time (not counting the recursive calls).

Upvotes: 1

kfx
kfx

Reputation: 8537

There is no need to use the Master theorem here.

Think of the problem this way: what is the maximum number of operations you have do for each node in the tree? It is bounded by a constant. And what the is the number of nodes in the tree? It is n.

The multiplication of constant with n is still O(n).

Upvotes: 0

Related Questions