title: Why Time complexity of permutation function is O(n!)
body: <p>Consider following code.</p>
  
  <pre class="lang-java prettyprint-override"><code>public class Permutations {
      static int count=0;
      static void permutations(String str, String prefix){
          if(str.length()==0){
              System.out.println(prefix);
          }
          else{
              for(int i=0;i&lt;str.length();i++){
                  count++;
                  String rem = str.substring(0,i) + str.substring(i+1);
                  permutations(rem, prefix+str.charAt(i));
              }
          }
  
      }
      public static void main(String[] args) {
          permutations("abc", "");
          System.out.println(count);
      }
  
  }
  </code></pre>
  
  <p>here the logic, that i think is followed is- it considers each character of the string as a possible prefix and permutes the remaining n-1 characters.
  <br> so by this logic recurrence relation comes out to be <br></p>
  
  <pre><code>T(n) = n( c1 + T(n-1) )          // ignoring the print time
  </code></pre>
  
  <p>which is obviously O(n!). but when i used a count variable to see wheather algo really grows in order of n!, i found different results.<br>
  for 2-length string for count++(inside for loop) runs 4 times, for 3-length string value of count comes 15 and for 4 and 5-length string its 64 and 325.<br>
  It means it grows worse than n!. then why its said that this(and similar algos which generate permuatations) are O(n!) in terms of run time.</p>