Time complexity analysis for recursion inside recursion

Question

I am a little confused of the time complexity of the code below:

public int getHeight(TreeNode root) {
    if (root == null) return 0;
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
public boolean isBalanced(TreeNode root) {
    if (root == null) return true;

    int heightDiff = getHeight(root.left) - getHeight(root.right);
    if (Math.abs(heightDiff) > 1) {
        return false;
    }
    else {
        return isBalanced(root.left) && isBalanced(root.right);
    }
}

I calculate the time as: T(n) = 2 * T(n / 2) + n, which gives me O(n * log(n)). But in the book, it says the time complexity is O(n ^ 2). Can anyone tell where my calculation is wrong? Thanks!

chepner · Accepted Answer · 2014-10-14 15:18:31Z

1

Your recurrence assumes that the tree is balanced, which would make isBalanced O(n lg n). It appears the book does not make that assumption, so isBalanced becomes O(n²). In the worst case, each internal node could have only one child (such a tree is sometimes called a vine, since it doesn't really branch at all).

For example, here is a worst-case input:

edited Oct 14, 2014 at 15:18

answered Oct 14, 2014 at 15:11

chepner

538k77 gold badges594 silver badges746 bronze badges

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

2 Comments

Optimus Over a year ago

Thank you. I think I got your idea. But then is there a way to calculate the complexity using a recurrence formula? It seems that by looking at the code, it is straightforward to get T(n) = 2 * T(n / 2) + n, which is wrong in this case.

chepner Over a year ago

I think the closest recurrence that would apply is T(n) = T(n-1) + T(1) + n. It captures the worst case behavior correctly, at the expense of ignoring the expected case. T(n/2) again assumes that each recursive call actually works on (roughly) half the data, which is not true of the worst case.

Collectives™ on Stack Overflow

Time complexity analysis for recursion inside recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related