1 votes 1 votes 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?? Algorithms algorithms recurrence-relation time-complexity + – srestha asked May 19, 2019 • recategorized Jul 6, 2022 by Lakshman Bhaiya srestha 636 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply ankitgupta.1729 commented May 19, 2019 reply Follow Share similar problem from Rosen 1 votes 1 votes srestha commented May 19, 2019 i edited by srestha May 19, 2019 reply Follow Share @ankitgupta.1729 yes base condition will be $T(0)=0$ $T(1)=01$ right?? 0 votes 0 votes Arkaprava commented May 20, 2019 reply Follow Share You can use dynamic programming to get the answer in $O(n)$ , since the recurrence is same as that of the Fibonacci one. 0 votes 0 votes ankitgupta.1729 commented May 20, 2019 reply Follow Share @srestha mam, $a_1=2$ because 0 and 1 are possible strings of size 1 where no consecutive 1 occurs 1 votes 1 votes srestha commented May 20, 2019 reply Follow Share but then it just a count of elements Here we want how recurrence grows right?? 0 votes 0 votes ankitgupta.1729 commented May 20, 2019 reply Follow Share recurrence is defined for 'no. of n bit strings where no two consecutive 1s occur' Please check the given pic and understand the meaning of $a_n, a_{n-1},a_{n-2}$ 0 votes 0 votes Please log in or register to add a comment.