time complexity

Question

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)$

Comments

N is size of string?

---

Please mention what kind of solution is being referred to.

---

@shubham yes N size of sting and upper bound to number of stings not time to find such strings

Answer 1

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

Comments

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}$

---

if we have n positions then we can have 2ⁿ strings with 0,1 which includes consecutive 0's so solutions must be less than 2ⁿ 

---

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