1 votes 1 votes let $S$ be a String containing either $0$ or $1$ .further there are no two consecutive $0s$ in $S$. No of solution on an input size $S(N)$ is bounded by $O(n^2)$ $O(nlogn)$ $O(2^n)$ $O(n)$ Algorithms algorithms time-complexity + – Akshay Nair asked Feb 13, 2018 • retagged Jun 10, 2022 by makhdoom ghaya Akshay Nair 593 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply smsubham commented Feb 13, 2018 reply Follow Share N is size of string? 0 votes 0 votes shashanksingh commented Feb 13, 2018 reply Follow Share Please mention what kind of solution is being referred to. 0 votes 0 votes Tesla! commented Feb 14, 2018 reply Follow Share @shubham yes N size of sting and upper bound to number of stings not time to find such strings 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes Recurrence for following is S(n)=S(n-1)+S(n-2) where S(0)=1 and S(1)=2 Above recurrence is nothing but Fibonacci series which is upper bounded by O($2^{n}$) thus C Tesla! answered Feb 13, 2018 Tesla! comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Tesla! commented Feb 19, 2018 reply Follow Share Count strings where no 2 consecutive zero are there manually Now you use above relationship and you will see manually counting and formula derive same thing Above recurrence is most famous Fibonacci recurrence, on simplifying solutions comes out to be 2$^{n}$ 1 votes 1 votes shivanisrivarshini commented Feb 19, 2018 reply Follow Share if we have n positions then we can have 2n strings with 0,1 which includes consecutive 0's so solutions must be less than 2n 0 votes 0 votes Tesla! commented Feb 19, 2018 reply Follow Share yes, definitely it is less than 2$^{n}$ but to find that particular number we need to execute above recurrence and the appxromiate solution is (1.6)$^{n}$ so to give it an upper bound we round off to 2$^{n}$ n=0 (1.6)$^{0}$=1 n=1 (1.6)$^{1}$=1.6 ->2 n=2 (1.6)$^{2}$=2.56-> 3 1 votes 1 votes Please log in or register to add a comment.