CODEWITHSUNDEEP
algorithmtime-complexity
Optimus
Optimus

Reputation: 23

Time complexity analysis for recursion inside recursion

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!

Upvotes: 2

Views: 132

Answers (1)

chepner
chepner

Reputation: 530920

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(n2). 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:

    1
     \
      \
       2
      /
     /
    3
   /
  /
 4
  \
   \
    5

Upvotes: 1

Related Questions