Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and the Yahoo Answers website is now in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

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

    =>

Still have questions? Get your answers by asking now.