I have two algorithms that solve this problem: Generate all sequences of bits within Hamming distance t. Now I want to compare them theoretically (I do have time measurements, if needed).
The iterative algorithm has a complexity of:
O((n choose t) * n)
where n is the length of the bit-string and t is the desired Hamming distance.
The recursive algorithm, they best we have so far is:
O(2^n)
but how to compare these two Time Complexities, without introducing t inside the second Time Complexity? For that reason, I am trying to do that, can you help?
The recursive algorithm:
// 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); } 
next_permutationon another vector of bits.changesLeft > iand return, you can return early if t is close to n.t, let's say ton/2and compute the Time Complexity of the function, this would be enough, I guess.