CODEWITHSUNDEEP
c#time-complexity
parsh
parsh

Reputation: 756

Time Complexity of the recursive for loop code

I have this code, 

void Generate(List<string> comb, string prefix, string remaining)
{
       int currentDigit = Int32.Parse(remaining.Substring(0, 1));

            if (remaining.Length == 1)
            {
                for (int i = 0; i < dictionary[currentDigit].Length; i++)
                {
                    comb.Add(prefix + dictionary[currentDigit][i]);
                }
            }
            else
            {
                for (int i = 0; i < dictionary[currentDigit].Length; i++)
                {
                    Generate(comb, prefix + dictionary[currentDigit][i], remaining.Substring(1));
                }
            }
}

What is the time complexity of the above code?

Is it Generate is O(n) and that itself is being executed n times so O(n^2)?

dictionary is len = 10 and has phone keypads stored it in. 2 = "abc" etc.

The initial call to this code will be like

Generate(new List(), "", "12345");

Thanks.

Upvotes: 3

Views: 525

Answers (1)

Saeed Amiri
Saeed Amiri

Reputation: 22555

Assume dictionary size is m and input string size is n (remaining) this will be:

T(1) = m + constant;
T(n) = m T(n-1) + O(n) ==> T(n) = O(m^n)

In fact in each running of else part, you will run m times, function of O(n).

Upvotes: 1

Related Questions