Estoy tratando de encontrar la complejidad del tiempo de estoalgoritmo.

El algoritmo iterativo: produce todas las cadenas de bits dentro de una distancia de Hamming dada, a partir de la cadena de bits de entrada. Genera todas las secuencias crecientes.0 <= a[0] < ... < a[dist-1] < strlen(num), y revierte bits en los índices correspondientes.

El vectora se supone que debe mantener índices para los que se deben invertir los bits. Entonces, si a contiene el índice actuali, imprimimos 1 en lugar de 0 y viceversa. De lo contrario, imprimimos el bit tal como está (vea la parte else), como se muestra a continuación:

// e.g. hamming("0000", 2);
void hamming(const char* num, size_t dist) {
    assert(dist > 0);
    vector<int> a(dist);
    size_t k = 0, n = strlen(num);
    a[k] = -1;
    while (true)
        if (++a[k] >= n)
            if (k == 0)
                return;
            else {
                --k;
                continue;
            }
        else
            if (k == dist - 1) {
                // this is an O(n) operation and will be called
                // (n choose dist) times, in total.
                print(num, a);
            }
            else {
                a[k+1] = a[k];
                ++k;
            }
}

¿Cuál es la complejidad del tiempo de este algoritmo?

Mi intento dice:

dist * n + (n elige t) * n + 2

pero esto no parece ser cierto, considere los siguientes ejemplos, todos con dist = 2:

len = 3, (3 choose 2) = 3 * O(n), 10 while iterations
len = 4, (4 choose 2) = 6 * O(n), 15 while iterations
len = 5, (5 choose 2) = 9 * O(n), 21 while iterations
len = 6, (6 choose 2) = 15 * O(n), 28 while iterations

Aquí hay dos ejecuciones representativas (con la impresión al inicio del ciclo):

000, len = 3
k = 0, total_iter = 1
vector a = -1 0 
k = 1, total_iter = 2
vector a = 0 0 
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1 
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2 
k = 0, total_iter = 5
vector a = 0 3 
k = 1, total_iter = 6
vector a = 1 1 
Paid O(n)
k = 1, total_iter = 7
vector a = 1 2 
k = 0, total_iter = 8
vector a = 1 3 
k = 1, total_iter = 9
vector a = 2 2 
k = 0, total_iter = 10
vector a = 2 3 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gsamaras@pythagoras:~/Desktop/generate_bitStrings_HammDistanceT$ ./iter
0000, len = 4
k = 0, total_iter = 1
vector a = -1 0 
k = 1, total_iter = 2
vector a = 0 0 
Paid O(n)
k = 1, total_iter = 3
vector a = 0 1 
Paid O(n)
k = 1, total_iter = 4
vector a = 0 2 
Paid O(n)
k = 1, total_iter = 5
vector a = 0 3 
k = 0, total_iter = 6
vector a = 0 4 
k = 1, total_iter = 7
vector a = 1 1 
Paid O(n)
k = 1, total_iter = 8
vector a = 1 2 
Paid O(n)
k = 1, total_iter = 9
vector a = 1 3 
k = 0, total_iter = 10
vector a = 1 4 
k = 1, total_iter = 11
vector a = 2 2 
Paid O(n)
k = 1, total_iter = 12
vector a = 2 3 
k = 0, total_iter = 13
vector a = 2 4 
k = 1, total_iter = 14
vector a = 3 3 
k = 0, total_iter = 15
vector a = 3 4