請問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

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

=>