edited by
510 views
1 votes
1 votes

The solution for the recurrence:

T(1)=1

T(n) = T(n-1) + T(n-2) + 1

a. log(n) <= T(n)=n

b. n<=T(n)<=n2

c. n2 <= T(n)<= 2n

d. 2n <= T(n) <=n!

edited by

1 Answer

0 votes
0 votes

n <= T(n)<= 2n

 

 

I think this is the answer and in fib series 1 is not there because, not combining at all in fib series.

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
0 answers
2
srestha asked May 19, 2019
594 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 Co...
1 votes
1 votes
2 answers
3
srestha asked May 10, 2019
844 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
1 votes
1 votes
1 answer
4
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$