The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
53 views
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??
asked in Algorithms by Veteran (111k points)
edited by | 53 views
+1

similar problem from Rosen

0

@ankitgupta.1729

yes base condition will be

$T(0)=0$

$T(1)=01$

right??

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 

0
but then it just a count of elements

Here we want how recurrence grows

right??
0
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}$

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,532 questions
54,123 answers
187,319 comments
71,044 users