GATE CS 2015 Set 1 Q49 — Asymptotic Worst Case Time and Space Complexity

To find the recurrence relation for $a_n$, the number of bit strings of length $n$ containing two consecutive $1$s, we can partition the set of valid strings of length $n$ based on their starting bits:

1. Case 1: The string starts with 0
   The remaining $n-1$ bits must contain two consecutive $1$s.
   Number of such strings = $a_{n-1}$
2. Case 2: The string starts with 10
   The remaining $n-2$ bits must contain two consecutive $1$s.
   Number of such strings = $a_{n-2}$
3. Case 3: The string starts with 11
   Since we already have two consecutive $1$s at the beginning, the remaining $n-2$ bits can be any arbitrary bit string of length $n-2$.
   Number of such strings = $2^{n-2}$

Since these three cases are mutually exclusive and collectively cover all valid strings of length $n$, we sum them up to get the recurrence relation:

This matches Option A.