1

I gave the following solution (I think the solution is ok, not sure), but couldn't analyze it's time complexity.

If anyone's interested, this is the question: (if not, skip to the code):

Your input is D - a set of words, and s - a string without spaces. Write a method to count the number of legal division of s, such that a legal division is defined as such that all the words that were partitioned from s are in D. For example, if D contains {run,time,runtime} then for s="runtime" the answer should be 2: the first one is the empty partition (meaning, just the word runtime) and the second one is partitioning s to "run" and "time"

This is my solution (pseudo):

int CountPartitions(string s)
{
    if (s.Length == 0)
        return 1;
    int result = 0;
    for (int i = 0; i < s.Length ; ++i)
    {
        string prefix = s.substring(0,i);
        if (D.cotains(prefix))
        {
            result += CountPartitions(s.substring(i+1,s.Length));
        }
    }
    return result;
}

The way I see it, the time complexity of the function is given by:

T(n) = T(n-1)+T(n-2)+...+T(1) Where T(1) is constant assuming that querying the dictionary can be done in constant time, however, I don't know how to solve this equation.

1 Answer 1

0

Your algorithm and the recurrence equation seems to be correct.

To compute the time-complexity you count the number of T(1) showing up in the expanded expression of T(n).

Let N(n) be the number of T(1)'s showing up in T(n) after expanding it.
e.g. T(3) = T(2) + T(1) = T(1) + T(1) so N(3) = 2.
I will use induction to prove N(n) = 2^(n-2) for all n >= 2

n = 1: T(1) = T(1) => N(1) = 1
n = 2: T(2) = T(1) => N(2) = 1 = 2^(2-2)
n = 3: T(3) = 2*T(1) => N(3) = 2 = 2^(3-2)

so let N(k) = 2^(k-2) be correct for all 2 < k <= n:

T(n+1) = T(n) + T(n-1) + ... + T(1) 
=> N(n+1) = N(n) + ... N(1)
          = 2^(n-2) + 2^(n-3) + ... 2^(n-n) + 1
          = ( 2(n-1) - 1 ) + 1
          = 2^(n-1)

So, now we know that N(n) = 2^(n-2) is correct. So the complexity of your algorithm is Θ(2^n).

If you only want to have upper or lower bounds you can use a trick:

n/2 * T(n/2) <= T(n) <= (n-1) * T(n-1)

This gives you easily the upper bound O((n-1)!) and the lower bound Ω(n^(log n)).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.