The Gateway to Computer Science Excellence
+1 vote
156 views

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!

in Algorithms by Active (1.8k points)
edited by | 156 views
0
I think it should be c.
0
yes c
0
fibonacci recurrence, will be O(2^n) ,multiple times you will be calling same problem again and again.
0
didn't get u
+1
the recurrence is that which generates fibonacci sequences,it is just that it calculates same subproblem many no of times that is why its complexity is exponential(just a thought which came in as I was reading dynamic programming,maybe you know this already....:)) ..you can draw a recursion tree to see why it happens so.

1 Answer

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.

by (11 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,365 answers
198,495 comments
105,263 users