title: Time Complexity of permutation function
body: <p>Given a collection of distinct numbers, return all possible permutations.</p>
  
  <blockquote>
    <p>For example, [1,2,3] have the following permutations:<br>
     [   [1,2,3],  [1,3,2],   [2,1,3],   [2,3,1],   [3,1,2],   [3,2,1] ]</p>
  </blockquote>
  
  <p>My Iterative Solution is :</p>
  
  <pre><code>public List&lt;List&lt;Integer&gt;&gt; permute(int[] nums) {
          List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;&gt;();
          result.add(new ArrayList&lt;&gt;());
          for(int i=0;i&lt;nums.length;i++)
          {
              List&lt;List&lt;Integer&gt;&gt; temp = new ArrayList&lt;&gt;();
              for(List&lt;Integer&gt; a: result)
              {
                  for(int j=0; j&lt;=a.size();j++)
                  {
                      a.add(j,nums[i]);
                      List&lt;Integer&gt; current = new ArrayList&lt;&gt;(a);
                      temp.add(current);
                      a.remove(j);
                  }
              }
              result = new ArrayList&lt;&gt;(temp);
          }
          return result;
      }
  </code></pre>
  
  <p>My Recursive Solution is:</p>
  
  <pre><code>public List&lt;List&lt;Integer&gt;&gt; permuteRec(int[] nums) {
          List&lt;List&lt;Integer&gt;&gt; result = new ArrayList&lt;List&lt;Integer&gt;&gt;();
          if (nums == null || nums.length == 0) {
              return result;
          }
          makePermutations(nums, result, 0);
          return result;
      }
  
  
  void makePermutations(int[] nums, List&lt;List&lt;Integer&gt;&gt; result, int start) {
      if (start &gt;= nums.length) {
          List&lt;Integer&gt; temp = convertArrayToList(nums);
          result.add(temp);
      }
      for (int i = start; i &lt; nums.length; i++) {
          swap(nums, start, i);
          makePermutations(nums, result, start + 1);
          swap(nums, start, i);
      }
  }
  
  private ArrayList&lt;Integer&gt; convertArrayToList(int[] num) {
          ArrayList&lt;Integer&gt; item = new ArrayList&lt;Integer&gt;();
          for (int h = 0; h &lt; num.length; h++) {
              item.add(num[h]);
          }
          return item;
      }
  </code></pre>
  
  <p>According to me the time complexity(big-Oh) of my iterative solution is: n * n(n+1)/2~ O(n^3)<br>
  I am not able to figure out the time complexity of my recursive solution.<br>
  Can anyone explain complexity of both?</p>