Big O Time Complexity for Recursive Pattern

Question

I have question on runtime for recursive pattern.

Example 1

int f(int n) {
  if(n <= 1) {
    return 1;
  }

  return f(n - 1) + f(n - 1);
}

I can understand that the runtime for the above code is O(2^N) because if I pass 5, it calls 4 twice then each 4 calls 3 twice and follows till it reaches 1 i.e., something like O(branches^depth).

Example 2 Balanced Binary Tree

int sum(Node node) {
  if(node == null) {
    return 0;
  }

  return sum(node.left) + node.value + sum(node.right);
}

I read that the runtime for the above code is O(2^log N) since it is balanced but I still see it as O(2^N). Can anyone explain it?

1. When the number of element gets halved each time, the runtime is log N. But how a binary tree works here?
2. Is it 2^log N just because it is balanced?
3. What if it is not balanced?

Edit: We can solve O(2^log N) = O(N) but I am seeing it as O(2^N).

Thanks!

Answer 1

• Binary tree will have complexity O(n) like any other tree here because you are ultimately traversing all of the elements of the tree. By halving we are not doing anything special other than calculating sum for the corresponding children separately.

• The term comes this way because if it is balanced then 2^(log_2(n)) is the number of elements in the tree (leaf+non-leaf).(log2(n) levels)

• Again if it is not balanced it doesn't matter. We are doing an operation for which every element needs to be consideredmaking the runtime to be O(n).

Where it could have mattered? If it was searching an element then it would have mattered (whether it is balanced or not).