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

Question

Я пытаюсь проанализировать сложность времени рекурсивного алгоритма, который решает проблему Generate all sequences of bits within Hamming distance t. Алгоритм таков:

// str is the bitstring, i the current length, and changesLeft the 
// desired Hamming distance (see linked question for more) 
void magic(char* str, int i, int changesLeft) { 
     if (changesLeft == 0) { 
       // assume that this is constant 
       printf("%s\n", str); 
       return; 
     } 
     if (i < 0) return; 
     // flip current bit 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft-1); 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft); 
} 

Какова временная сложность этого алгоритма?

---

Я люблю себя довольно ржавый, когда дело доходит до этого, и вот моя попытка, которую я чувствую, не где близок к истине:

t(0) = 1 
t(n) = 2t(n - 1) + c 
t(n) = t(n - 1) + c 
    = t(n - 2) + c + c 
    = ... 
    = (n - 1) * c + 1 
    ~= O(n) 

где n длина битовой строки.

Вопросы, относящиеся: 1, 2.

Answer 1

Это экспоненциальный:

t(0) = 1 
t(n) = 2 t(n - 1) + c 
t(n) = 2 (2 t(n - 2) + c) + c   = 4 t (n - 2) + 3 c 
    = 2 (2 (2 t(n - 3) + c) + c) + c = 8 t (n - 3) + 7 c 
    = ... 
    = 2^i t(n-i) + (2^i - 1) c   [at any step i] 
    = ... 
    = 2^n t(0) + (2^n - 1) c   = 2^n + (2^n - 1) c 
    ~= O(2^n) 

Или, используя WolframAlpha: https://www.wolframalpha.com/input/?i=t(0)%3D1,+t(n)%3D2+t(n-1)+%2B+c

Причина это экспонента, что ваши рекурсивные вызовы уменьшения размера задачи на 1, но вы делаете два рекурсивную звонки. Ваши рекурсивные вызовы формируют двоичное дерево.