[理工] [資結] 一題用代入替換法求複雜度

[skill91002 (有為)]

題目如下:

                                  1/2
Solving the recurrence T(n) = 2T(n   ) + lg n using big-O notation

as tight as possible.


小弟解到一半卡住了

不知道最終要做到何時停

翻了一下解答

解答說 T(2) = 1

有了這個假設我就會了

可是請問為何 T(2) = 1 ?

謝謝各位大大!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.117.120.229
推 jameschou:因為初始條件如果是給T(1)或T(0) 你沒有辦法借由1/2次方
→ jameschou:達到 所以有開幾次方 而不是除以多少的話 初值都會定在
→ jameschou:T(2)以上
→ skill91002:恩恩了解 謝謝詹姆士大大
推 DavyBlue:其實T(2)=C就可以了 那個常數不重要
→ skill91002:對了那如果是3次根號或是以上 條件會變什麼？y