similar problem from Rosen

The Gateway to Computer Science Excellence

+1 vote

Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Complexity??

0

You can use dynamic programming to get the answer in $O(n)$ , since the recurrence is same as that of the Fibonacci one.

+1

@srestha mam, $a_1=2$ because 0 and 1 are possible strings of size 1 where no consecutive 1 occurs

52,215 questions

59,993 answers

201,196 comments

94,663 users