title: Complexity of factorial recursive algorithm
body: <p>Today in class my teacher wrote on the blackboard this recursive factorial algorithm:</p>
  
  <pre><code>int factorial(int n) {
     if (n == 1) 
         return 1;
     else 
         return n * factorial(n-1);
  }
  </code></pre>
  
  <p>She said that it has a cost of <code>T(n-1) + 1</code>. </p>
  
  <p>Then with iteration method she said that <code>T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j</code>, so the algorithm stops when <code>n - j = 1</code>, so <code>j = n - 1</code>.</p>
  
  <p>After that, she substituted <code>j</code> in <code>T(n-j) + j</code>, and obtained <code>T(1) + n-1</code>.</p>
  
  <p>She directly said that for that n-1 = 2<sup>(log<sub>2</sub>n-1)</sup>, so the cost of the algorithm is exponential.</p>
  
  <p>I really lost the last two steps. Can someone please explain them to me? </p>