請問complexity的問題.

suppose

T(N) =

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

{ 1 , n=1

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

1 Answer

Rating
  • 鴨子
    Lv 6
    1 decade ago
    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 answers
Still have questions? Get your answers by asking now.