title: How to analyse the time complexity of the following code?
body: <p>Is it <code>O(n^6)</code> or <code>O(n!)</code>?</p>
  
  <pre><code>public boolean isScramble(String s1, String s2) { 
      return isScramble(s1, 0, s1.length(), s2, 0); 
  } 
  
  private static boolean isScramble(String s1, int begin1, int end1,
                                    String s2, int begin2) { 
      final int length = end1 - begin1; 
      final int end2 = begin2 + length; 
  
      if (length == 1) return s1.charAt(begin1) == s2.charAt(begin2); 
  
      for (int i = 1; i &lt; length; ++i) 
          if ((isScramble(s1, begin1, begin1 + i, s2, begin2) &amp;&amp; 
               isScramble(s1, begin1 + i, end1, s2, begin2 + i)
              ) || 
              (isScramble(s1, begin1, begin1 + i, s2, end2 - i) &amp;&amp; 
               isScramble(s1, begin1 + i, end1, s2, begin2))) 
             return true; 
  
      return false; 
  } 
  </code></pre>
  
  <p>Analysis:</p>
  
  <pre><code>T(1) = 1
  T(n) = (T(1) + T(n-1)) * 2 + (T(2) + T(n-2)) * 2 + ....
       =~ T(1) + T(2) + ... + T(n-1)
  </code></pre>