Сложность времени рекурсивного кода цикла

Question

У меня есть этот код,

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));
                }
            }
}

Какова временная сложность вышеприведенного кода?

Является ли это Generate O (n) и что само выполняется n раз, такO (n ^ 2)?

словарь len = 10 и имеет телефонные клавиатуры, в которых он хранится. 2 = "abc" и т. Д.

Первоначальный вызов этого кода будет выглядеть как

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

Спасибо.

Answer 1

Предполагается, что размер словаря m, а размер входной строки n (остальное):

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

Фактически при каждом запуске детали else вы будете запускать m раз, функция O (n).