I am stuck with following proof which I am not able to get.
One such code is a list of $2n$ $n$-bit strings in which each string (except the first) differs from the previous one in exactly one bit. Let us call such a list a twiddling list since we go from one string to the next by just flipping one bit.
Consider the following recursive algorithm for listing the $n$-bit strings of a twiddling list. If $n = 1$, the list is $0,1$. If $n > 1$, first take a twiddling list of $(n − 1)$-bit strings and place a $0$ in front of each string. Then, take a second copy of the twiddling list of $(n − 1)$-bit strings, place a $1$ in front of each string, reverse the order of the strings and place it after the first list. So, for example, for $n = 2$, the list is $00,01,11,10$, and for $n = 3$, we get $000,001,011,010,110,111,101,100$.
I need to prove it by induction on n such that every n-bit string appears exactly once in the list generated by the algorithm. Also, what will be the worst case time complexity of this recurrence relation.