Temporal complexity of a recursive solution for break break?

Question

What is the time complexity of the recursive solution of this in the code taken from: http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/ :

// 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<=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) ) &&
            wordBreak( str.substr(i, size-i) ))
            return true;
    }

    // If we have tried all prefixes and none of them worked
    return false;
}

I think its n ^ 2, because for n method calls, this worst case (n-1) works (iterating over the rest of the string recursively?). Or is it exponentially / n !?

It's hard for me to understand Big (O) recursive functions like these. Any help is much appreciated!

Answer 1

The answer is exponential , to be precise O(2^(n-2)).(2 power n-2)

1,2....n-1 ( ). n, n-1, n-2, ..... 1. , T (n) - , sum of T(n-1),T(n-2)....T(1).

:

  T(n) = T(n-1) + T(n-2) +.....T(1);
  T(1) = T(2) = 1 

, , - .

  T(1) = T(2) = 1
  T(3) = T(1) + T(2) = 1+1 =2; // 2^1
  T(4) = T(1)+ T(2) + T(3) = 1+1+2 =4; //2^2
  T(5) = T(1) + T(2) +T(3) +T(4) = 1+1+2+4 =8; //2^3

, , , 2^(n-2)