title: Understanding Big O notation - Cracking the coding interview example 9
body: <p>I got stuck with this two codes.</p>
  
  <p><strong>Code 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><strong>Code 2</strong> (Balanced binary search tree)</p>
  
  <pre><code>int sum(Node node){
      if(node == null){
          return 0;
      }
      return sum(node.left) + node.value + sum(node.right);
  }
  </code></pre>
  
  <p>the author says the runtime of Code 1 is O(2^n) and space complexity is O(n)</p>
  
  <p>And Code 2 is O(N)</p>
  
  <p>I have no idea what's different between those two codes. it looks like both are the same binary trees</p>