Time complexity of the word break recursive solution?

Question

What is the time complexity of the recursive solution to 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'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!?

I'm having a tough time figuring out Big(O) of recursive functions such as these. Any help is much appreciated!

Answer 1

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

In each call you are calling the recursive function with length 1,2....n-1(in worst case). To do the work of length n you are recursively doing the work of all the strings of length n-1, n-2, ..... 1. So T(n) is the time complexity of your current call, you are internally doing a work of sum of T(n-1),T(n-2)....T(1).

Mathematically :

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

If you really don't know how to solve this, an easier way to solve the above recurrence is by just substitute values.

  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

So if you substitute first few values, it will be clear that the Time complexity is 2^(n-2)