GATE CS 2008 Q78 — Asymptotic Worst Case Time and Space Complexity

To find the recurrence relation for $x_n$, the number of binary strings of length $n$ containing no consecutive $0$s, we can analyze the structure of any valid string of length $n$ based on its ending character:

• Case 1: The string ends with '1'
  If the last character is '1', the preceding $n-1$ characters can be any valid binary string of length $n-1$ with no consecutive $0$s.
  The number of such strings is $x_{n-1}$.
• Case 2: The string ends with '0'
  Since the string cannot contain consecutive $0$s, the character immediately preceding the last '0' must be '1' (for $n \ge 2$). Thus, the string must end with '10'.
  The remaining prefix of length $n-2$ can be any valid binary string of length $n-2$ with no consecutive $0$s.
  The number of such strings is $x_{n-2}$.

Since these two cases are mutually exclusive and exhaustive, we sum them to get the total count:

Verification with small values:

• For $n = 1$: Valid strings are 0, 1 $\implies x_1 = 2$.
• For $n = 2$: Valid strings are 01, 10, 11 $\implies x_2 = 3$.
• For $n = 3$: Valid strings are 010, 011, 101, 110, 111 $\implies x_3 = 5$.

Using the recurrence relation: $x_3 = x_2 + x_1 = 3 + 2 = 5$, which perfectly matches the manual count.

Therefore, the correct option is D.