http://i.imgur.com/ap9FhYW.jpg
请问第一小题怎么算，答案是O(2^n)
我列的时间方程式是T(n)=T(n-1)+T(n-2)+3，3是两个乘和一个加
不知道有没有列错，谢谢

没列错，用夹的看看？上限是 T(n)=2T(n-1)+3下限是T(n)=2T(n-2)+3,会在这两个中间，这两个都是2^n吧

http://i.imgur.com/fMan9Xf.jpg 用递回树加猜测可以得出O(2^n) 但是用离散的做法应该才叫最tight的http://i.imgur.com/6CWzL0l.jpg 离散算出来的bounded跟原本的费氏数列一样就是黄金比例的n次方所以我觉得答案有瑕疵0.0

谢谢楼上两位！