0
$\begingroup$

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research it is $O(n)$. Can you show it how come and my wrong?

void printInorder(Node node) 
    { 
        if (node == null)     // I think it is T(0) = 1
            return;           // constant c

        /* first recur on left child */
        printInorder(node.left);     // T(n-1)

        /* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

        /* now recur on right child */
        printInorder(node.right); //T(n-1)
    } 
$\endgroup$
3
$\begingroup$

In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity is $O(n)$.

Here, the input is in terms of number of nodes in the tree and hence the complexity.

The notion that each recursive call is $T(n-1)$ is wrong. Let say we have a tree that has three children to the left of root and three children to the right of root. So n = 7. Now when you visit root then you have two paths. One to left which has 3 children and one to right which also has 3 children. But $7-1 \neq 3$. Hence this notion of 2 recursive calls of $T(n-1)$ is wrong.

It totally depends on the structure of the tree. In worst case a tree may degenerate to linked list (a skew tree having children on only one side either left or right) and we know well that traversal of linked list is $O(n)$, for a list of n elements. Hence, also the worst case is $O(n)$.

$\endgroup$
0
$\begingroup$

The Big-O notation in simple terms could be said as the number of operations performed.

In the recursive function of yours, there are no internal loopings that add to an additional degree of operations. You may trace out this function and see how many times the function call happens which will make you more clear on understanding the recursive function.

Breaking down your function, for each time printInorder(n) is called,

  • checks if n is null
  • calls printInorder on n -> leftNode
  • prints n -> value
  • calls printInorder on n -> right node

So for every call of this function with a particular n a maximum of 4 operations are performed. (it will either be 4 if n != null and 1 if n == null). When you trace down the function on any binary tree, you may notice that the function call happens for (only) a single time on each node in the tree. So you can say a max of k*n operations (k << n, k <= 4 in this case) have been done in this function and so in terms of Big-O has an O(n) complexity.

$\endgroup$
0
$\begingroup$

Let $\ell_x$ be the left sub tree at node $x$, Let $r_x$ be the right sub tree at node $x$. So the size of $\ell_x$ is $\mid\ell_x\mid$, and size of $r_x$ is $\mid r_x\mid$.

Let $T(n)$ be number of nodes our procedure visited during in-order traversal.

So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r_x\mid)$, because we discard right sub tree at node $x$ and just recurs on left sub tree at node $x$. Additionally, we don't traverse $x$, so the recursive formula to describe the time complexity of this line of your code is

/* first recur on left child */
        printInorder(node.left);

$T(n-1-\mid \ell_{node}\mid)$.

consequently, recursive formula to describe the next recurs in your code is

/* now recur on right child */
        printInorder(node.right); 

$T(n-1-\mid r_{node}\mid)$.

The line

/* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

needs constant time. As a result we can write $T(n)$ as follow:

$$T(n)=T(n-1-\mid r_{node}\mid)+T(n-1-\mid \ell_{node}\mid)+1$$

I think above relation can be proved that $T(n)=\Theta(n)$, by induction. But i have no idea at this point.

So it not as the same recurrence relation that you write.

A simply analysis for such a situation is, the procedure visit each node only at once, So the running time is $\Theta(n)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.