Time and Space complexity?

#1

what is the time and space complexity of optimal binary strings recursion ?

#2

hello @namangarg31
time complexity -> O(2^n)
space complexity willl be O(n)

#3

sir can you please explain the time complexity i.e why it is 2^n ?

#4

T(n)=T(n-1)+T(n-2)
T(n-2) is nearly equal to T(n-1)
so we can write this as
T(n)=2 * T(n-1)
T(n-1)=2 * T(n-2) -> eq 2
T(n-2)=2 * T(n-3) - > eq 3
T(n-3)=2 * T(n-4) - > eq 4

…
…
…
T(n-(n-1) ) = 1. eq-> n
multiply eq 2 by 2 , eq 3 by 2^2, ,eq 4 by 2^3 , ,… eq n by 2 * (n-1) .
add all the equations.
u will get O(2^n)