Time Complexity of the recursive for loop code

Question

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.

It seems to depend on dictionary[currentDigit], not posted. — Henk Holterman
– Henk Holterman, Commented Nov 27, 2011 at 19:14
what is n? is remaining initial size? I guess your dictionary size is 10 at most. — Saeed Amiri
– Saeed Amiri, Commented Nov 27, 2011 at 19:17
Posted the dictionary[size]. FYI - this code is from a answer in SO, so was interested in understanding the time complexity of it. — parsh
– parsh, Commented Nov 27, 2011 at 19:29

Saeed Amiri · Accepted Answer · 2011-11-27 19:57:46Z

1

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).

edited Nov 27, 2011 at 19:57

answered Nov 27, 2011 at 19:19

Saeed Amiri

22.6k5 gold badges49 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

sll Over a year ago

Sorry I've overlooked that this is recursive method

parsh Over a year ago

@saeeda-amiri - I didn't get your last sentence, how did it change to O(mn^n)? Shouldnt it still stay as O(m^n)

Saeed Amiri Over a year ago

@parsh yes you are right, I'll edit it as first, but If you want to comment for someone, in his answer or post there is no need to use @. Also if this answers your question mark it as answer.

parsh Over a year ago

Sorry posting for the first time, will try to catch up to the rules.

Saeed Amiri Over a year ago

@parsh no matter dude, and these aren't rule, just hint to do your job faster and cleaner.

Collectives™ on Stack Overflow

Time Complexity of the recursive for loop code

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related