Advance test algorithms

Question

 

Comments

 Prince Sindhiya 

where did u get this question from???

---

What is the answer given ..

Is it O(n²) or O(${2^n}$). ??

---

Please add the source of question

Answer 1

For 0 bits(empty letter) : 1 possibility

For 1 bit : 0, 1 : 2 possibilities

For 2 bits : 00, 01, 10 : 3 possibilities

For 3 bits : 000, 001, 010, 100, 101 : 5 possibilities

For 4 bits : 8 possibilities

So to generalise, T(n) = T(n-1) + T(n-2) which accounts for O(2^n).