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

To find the number of binary strings of length $n$ with no consecutive $0$s, we can set up a recurrence relation based on the ending bit of the string:

• Case 1: The string ends with 1. The remaining $n-1$ bits can be any valid string of length $n-1$ with no consecutive $0$s. There are $x_{n-1}$ such strings.
• Case 2: The string ends with 0. To avoid consecutive $0$s, the second-to-last bit must be 1. The remaining $n-2$ bits can be any valid string of length $n-2$ with no consecutive $0$s. There are $x_{n-2}$ such strings.

This gives the recurrence relation:

Let's calculate the base cases directly:

• For $n = 1$: Valid strings are 0 and 1 $\implies x_1 = 2$.
• For $n = 2$: Valid strings are 01, 10, and 11 $\implies x_2 = 3$.

Using the recurrence relation, we compute the subsequent terms:

• $x_3 = x_2 + x_1 = 3 + 2 = 5$
• $x_4 = x_3 + x_2 = 5 + 3 = 8$
• $x_5 = x_4 + x_3 = 8 + 5 = 13$

The correct mathematical value for $x_5$ is 13. Since $13$ is not present in the given options (Option D is listed as 16), this question has no correct option, leading to the official answer key being marked as X (Marks to All).