title: Time complexity of the word break recursive solution?
body: <p>What is the time complexity of the recursive solution to this in the code taken from: <a href="http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/" rel="noreferrer">http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/</a> :</p>
  
  <pre><code>// returns true if string can be segmented into space separated
  // words, otherwise returns false
  bool wordBreak(string str)
  {
      int size = str.size();
  
      // Base case
      if (size == 0)  return true;
  
      // Try all prefixes of lengths from 1 to size
      for (int i=1; i&lt;=size; i++)
      {
          // The parameter for dictionaryContains is str.substr(0, i)
          // str.substr(0, i) which is prefix (of input string) of
          // length 'i'. We first check whether current prefix is in
          // dictionary. Then we recursively check for remaining string
          // str.substr(i, size-i) which is suffix of length size-i
          if (dictionaryContains( str.substr(0, i) ) &amp;&amp;
              wordBreak( str.substr(i, size-i) ))
              return true;
      }
  
      // If we have tried all prefixes and none of them worked
      return false;
  }
  </code></pre>
  
  <p>I'm thinking its n^2 because for n calls to the method, it worst case does (n-1) work (iterates over the rest of string recursively?). Or is it exponential/n!?</p>
  
  <p>I'm having a tough time figuring out Big(O) of recursive functions such as these. Any help is much appreciated!</p>