The Gateway to Computer Science Excellence
+1 vote

The solution for the recurrence:


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
I think it should be c.
yes c
fibonacci recurrence, will be O(2^n) ,multiple times you will be calling same problem again and again.
didn't get u
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....:)) 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
105,263 users