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.
Trending News
Promoted
請問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 61 decade agoFavorite 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.