Big O notation - recursion

Question

Found this algorithm online, I can't work out how to do the maths to find its complexity. I do understand its worst case is 2^n

// A simple recursive function to check whether C is an interleaving of A and B
bool isInterleaved(char *A, char *B, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *B || *C))
        return true;

    // If C is empty and any of the two strings is not empty
    if (*C == '\0')
        return false;

    // If any of the above mentioned two possibilities is true,
    // then return true, otherwise false
    return ( (*C == *A) && isInterleaved(A+1, B, C+1))
           || ((*C == *B) && isInterleaved(A, B+1, C+1));
}

Answer 1

See if you can reduce the problem by splitting the return into more lines,

// A simple recursive function to check whether C is an interleaving of A and B
bool isInterleaved(char *A, char *B, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *B || *C))
        return true;

    // If C is empty and any of the two strings is not empty
    if (*C == '\0')
        return false;

    // If any of the above mentioned two possibilities is true,
    // then return true, otherwise false
    if ((*C == *A) && isInterleaved(A+1, B, C+1))
        return true;
    return (*C == *B) && isInterleaved(A, B+1, C+1);
}

"Factor out" B to produce two methods

bool isInterleavedA(char *A, char *C)
{
    // Base Case: If all strings are empty
    if (!(*A || *C))
        return true;

    // If C is empty and any of the two strings is not empty
    if (*C == '\0')
        return false;

    // If any of the above mentioned two possibilities is true,
    // then return true, otherwise false
    return (*C == *A) && isInterleavedA(A+1, C+1);
}

bool isInterleavedB(char *A, char *B, char *C)
{
    bool result = isInterleavedA(A, C);
    if (!(*B) && result)
        return true;
    return (*C == *B) && isInterleavedB(A, B+1, C+1);
}

Now we can see isInterleavedA is O(n) and the BigOh isInterleavedB will be the same as isInterleaved, which will be.. N + MN?

Answer 2

Consider the complexity as a function of the number n of characters in C. Let's call that f(n).

The first if blocks are just doing simple checks no matter what, so we can ignore them for now (constant complexity).

The meat of the algorithm is of course these lines:

((*C == *A) && isInterleaved(A+1, B, C+1)) || ((*C == *B) && isInterleaved(A, B+1, C+1));

Checks (*C == ...) are again constant time complexity. Now, isInterleaved(..., ..., C+1) is calling the algorithm with a C shorter by 1: it's complexity is therefore f(n-1).

We can then put it all together as:

f(n) = k1 + (k2 + f(n-1)) + (k3 + f(n-1))

With k1, k2 and k3 being some constants. Reorder the terms, we get: f(n) = 2 * f(n-1) + k

Where k is, again, some constant. Now, expanding the recursion, we get:

f(n) = 2 * (2 * ( 2 * (... f(0) + k0) + k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2*(f(0) + k0) + k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2^2*(f(0) + k0) + 2*k1) + k2) + ... + k_n) = 2 * (2 * (2 * (... 2*(2^3*(f(0) + k0) + 2^2*k1 + 2*k2) + ... + k_n) f(n) = 2^n * (f(0) + k0) + 2^(n-1) * k1 + 2^(n-2) * k2 + ... Dividing that all by 2^n, we get:

f(n) / 2^n = (f(0) + k0) + k1 / 2 + k2 / 4 + ... + k_n / 2^n All of these terms are bounded: It is a property of the sum of 2^{-n} that it will approach 2 without ever reaching it, no matter how many terms you sum. Now, since all your k constants are just simple checks, it makes sense that they are also all bounded. Therefore, we know that there exist some constant K such that k0 < K, k1 < K, ..., k_n < K. Your f(n)/2^n then becomes:

f(n) / 2^n < f(0) + K * (1 + 1/2 + 1/4 + ... + 1/2^n)

Now, the first two checks ensure that f(0) is constant as well, so you have proven that the complexity of that function divided by 2^n is indeed bounded, which is sufficient to say that f(n) is O(2^n).

You can skim over most of these 'there exists a constant such that...'; the main observation to make is (using the 'handwavily equivalent-ish' symbol ~):

f(n) ~ f(n-1) + f(n-1) f(n) ~ 2 * f(n-1) f(n) ~ O(2^n) I have also slightly cheated by starting from the assumption that the length of C is the only parameter that matters for computing the complexity, but how you can rigorously show that the complexity is equivalent for various lengths of A and B is left as an exercise to the reader !

Answer 3

Consider the following case.

A = "ab"
B = "aa"
C = "aa"

now the recursion will be executed as below,

fn(ab, aa, aa)
=> fn(b, aa, a) + fn(ab, a, a)
=> false + fn(b, a, null) + fn(b, null, a) + fn(ab, null, null)

number of function call is 6.

Now if you add a single a at the first for all of them, like

A = "aab"
B = "aaa"
C = "aaa"

you will see this time number of function call will be 14.

add similarly one a more. then it will be 30.. then 62 then ... you can see its simply 2^n - 2. or like so.

So the actual complexity here is 2^n not n^2.

This is happening because you are not using memorization here.