請問complexity的問題.

Question

suppose

T(N) =

{ 2T(n-1) , n>=2 ,

{ 1 , n=1

please show that the complexity of T(n) is O(2^n)

Answer 1

Favorite Answer

T(1) = 1 = 2^0

T(2) = 2T(2-1) = 2T(1) = 2^1

T(3) = 2T(2) = 2^2

T(4) = 2T(3) = 2^3

........

T(m) = 2^(m-1)

=>

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

=>

當 n>=2, T(n)=1/2 * 2^n

所以, the complexity of T(n) = O(2^n).......根據 BigO的定義

2009-03-24 09:47:04 補充：

這邊修正一下

........

=>

T(n) = 2^(n-1), n>=1

=>

• Login to reply the answersPost