title: Big O Time Complexity for Recursive Pattern
body: <p>I have question on runtime for recursive pattern.</p>
  
  <p><strong>Example 1</strong></p>
  
  <pre><code>int f(int n) {
    if(n &lt;= 1) {
      return 1;
    }
  
    return f(n - 1) + f(n - 1);
  }
  </code></pre>
  
  <p>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).</p>
  
  <p><strong>Example 2</strong>
  <strong>Balanced Binary Tree</strong></p>
  
  <pre><code>int sum(Node node) {
    if(node == null) {
      return 0;
    }
  
    return sum(node.left) + node.value + sum(node.right);
  }
  </code></pre>
  
  <p>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?</p>
  
  <ol>
  <li>When the number of element gets halved each time, the runtime is log N. But how a binary tree works here?</li>
  <li>Is it 2^log N just because it is balanced?</li>
  <li>What if it is not balanced?</li>
  </ol>
  
  <p><strong>Edit:</strong>
  We can solve O(2^log N) = O(N) but I am seeing it as O(2^N).</p>
  
  <p>Thanks!</p>