CODEWITHSUNDEEP
pythonrecursionbig-otime-complexity
buydadip
buydadip

Reputation: 9407

break-down complexity of BST traversal

I have the following BST traversal function in Python:

def print_tree(tree):
    if tree == None:
        return
    else:
        print tree.value
        print_tree(tree.left)
        print_tree(tree.right)

The worst-case time complexity is O(n), but I am having a hard time proving it. I am attempting to break it down using constants, c, this is what I have:

T(n) = 2T(n-1) + cn

Where T(n) for both recursive calls, and cn for the print statement. But this does not seem to be correct.

Upvotes: 1

Views: 158

Answers (2)

NPE
NPE

Reputation: 500187

Just expand the recurrence relation:

T(1) = c*n
T(2) = 3*c*n
T(3) = 7*c*n
T(4) = 15*c*n
...

As you can see, you never get terms than are not linear in n.

Intuitively, the complexity is linear since you do a constant amount of work per node and never visit a node more than once.

If the tree is balanced, the recurrence relation becomes

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

and can be solved using the the master theorem (Case 1) to give O(n).

Upvotes: 2

levi
levi

Reputation: 22697

The recurrence relation should be 

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

Then from this answer you can solve your recurrence relation. Let's assume that cn = Θ(1)

T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

Upvotes: 2

Related Questions