Need to find Time and Space complexity of my algorithm

Question

Somehow i have managed to write an algorithm for Constructing a binary tree from it's inorder and preorder traversal data.

I am not sure how to compute time and space complexity of this algorithm.

My guess is

first pass  --> n(findInNode) + n/2 (constructTree) + n/2 (constructTree)
second pass --> n/2(findInNode) + n/4 (constructTree) + n/4 (constructTree)
etc..

So it should be approx(3logn)

Please correct me if i am wrong.

public class ConstructTree {
    public static void main(String[] args) {
        int[] preOrder = new int[] { 1, 2, 3, 4, 5 };
        int[] inOrder = new int[] { 2, 1, 4, 3, 5 };

        int start = 0;
        int end = inOrder.length -1;
        Node root =constructTree(preOrder, inOrder, start, end);

        System.out.println("In order Tree"); root.inOrder(root);
        System.out.println("");
        System.out.println("Pre order Tree"); root.preOrder(root);
        System.out.println("");

    }

    public static int preInd = 0;
    public static Node constructTree(int[] pre, int[] in, int start, int end) {
        if (start > end) {
            return null;
        }

        int nodeVal = pre[preInd++];
        Node node = new Node(nodeVal);
        if (start != end) {
            int ind = findInNode(nodeVal, in, start, end);
            node.left = constructTree(pre, in, start, ind-1);
            node.right = constructTree(pre, in, ind+1, end);
        }
        return node;
    }

    public static int findInNode(int nodeVal, int[] in, int start, int end) {
        int i = 0;
        for (i = start; i <= end; i++) {
            if(in[i] == nodeVal)
            {
                return i;
            }
        }
        return -1;
    }

}

How can this be sublinear if you insert all elements in the tree ??? At least O(N), with closed eyes. — user1196549
– user1196549, Commented Jul 2, 2012 at 19:06

Gumbo · Accepted Answer · 2012-07-02 21:11:01Z

1

To estimate the runtime complexity, let’s start off with the easy one, findInNode:

T_findInNode = Ο(n)

Estimating constructTree is a little more difficult since we have recursive calls. But we can use this pattern to split the … into local and recursive costs:

With each call of constructTree we have local costs of T_findInNode = Ο(n) and two recursive calls of constructTree with n-1 instead of n. So

T‍_{constructTree}(n) = T_findInNode(n) + 2 · T_{constructTree}(n-1))

Since the number of recursive calls of constructTree is doubled with every call of constructTree, the recursive call tree grows with each recursion step as follows:

                  n                    | 2^0·n = 1·n
         _________|_________           |
        |                   |          |
       n-1                 n-1         | 2^1·n = 2·n
    ____|____           ____|____      |
   |         |         |         |     |
  n-2       n-2       n-2       n-2    | 2^2·n = 4·n
  / \       / \       / \       / \    |
n-3 n-3   n-3 n-3   n-3 n-3   n-3 n-3  | 2^3·n = 8·n

So the total number of calls of constructTree after the initial call of constructTree is n, after the first step of recursive calls it is n+2·n calls, after the second step it is n+2·n+4·n, and so on. And since the total depth of this recursive calls tree is n (with each recursion n is decremented by 1), the number of total calls of constructTree sums up to:

2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹-1

Thus:

T‍_{constructTree}(n) = (2ⁿ⁺¹-1)·n ∈ Ο(2ⁿ).

So your algorithm has an exponential time complexity.

The space complexity is also Ο(2ⁿ) since you have a local space cost of 1 per recursive call of constructTree.

edited Jul 2, 2012 at 21:11

answered Jul 2, 2012 at 20:54

Gumbo

657k112 gold badges792 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user1168577 Over a year ago

I disagree with the analysis of deriving the complexity. The 2 recursive calls are constructing the binary tree, so in the end they construct n nodes. And the search takes O(n) for each node constructed. Hence the complexity is O(n^2).

user1168577 · Accepted Answer · 2012-07-03 03:07:06Z

0

Time complexity = O(n^2). 2 recursive calls take O(n) to construct the binary tree with each node construction taking O(n) for a sequential search which is O(n^2).

Space complexity = constant ignoring the 2 input arrays and the constructed binary tree which is the output

edited Jul 3, 2012 at 3:07

answered Jul 2, 2012 at 18:58

user1168577

1,98311 silver badges15 bronze badges

Collectives™ on Stack Overflow

Need to find Time and Space complexity of my algorithm

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related