Big O Time Complexity for Recursive Pattern

user_991086 0
Viewed 1413

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!

recursion big-o time-complexity algorithm
2 Answers

  • 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).

user_37961130

I'll take a stab at this.

In a balanced binary tree, you should have half the child nodes to the left and half to the right of each parent node. The first layer of the tree is the root, with 1 element, then 2 elements in the next layer, then 4 elements in the next, then 8, and so on. So for a tree with L layers, you have 2^L - 1 nodes in the tree.

Reversing this, if you have N elements to insert into a tree, you end up with a balanced binary tree of depth L = log_2(N), so you only ever need to call your recursive algorithm for log_2(N) layers. At each layer, you are doubling the number of calls to your algorithm, so in your case you end up with 2^log_2(N) calls and O(2^log_2(N)) run time. Note that 2^log_2(N) = N, so it's the same either way, but we'll get to the advantage of a binary tree in a second.

If the tree is not balanced, you end up with depth greater than log_2(N), so you have more recursive calls. In the extreme case, when all of your children are to the left (or right) of their parent, you have N recursive calls, but each call returns immediately from one of its branches (no child on one side). Thus you would have O(N) run time, which is the same as before. Every node is visited once.

An advantage of a balanced tree is in cases like search. If the left-hand child is always less than the parent, and the right-hand child is always greater than, then you can search for an element n among N nodes in O(log_2(N)) time (not 2^log_2(N)!). If, however, your tree is severely imbalanced, this search becomes a linear traversal of all of the values and your search is O(N). If N is extremely large, or you perform this search a ton, this can be the difference between a tractable and an intractable algorithm.

user_24645970
Related