[問題] 97中山資結

[depend (depend)]

中山資結的第一題
T(n)= 1                    if n=1
      4T(n/2)+theta(n^2)   if n>1
設T(n)=O(n^2)
=>T(n)=4O(n^2/2^2)+n^2=O(n^2)

這個步驟是哪裡出錯呢???

那正確的複雜度應該要怎麼算阿
我用數學的方法計算可是怎麼算都不是n^2*(logn)耶...??

麻煩高手解答 謝謝>"<

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.116.142.19
→ xmisery:master theorem; n^(log2 4)=n^2=θ(n^2)
→ xmisery:∴T(n)=θ( (n^2)*logn )
→ depend:可是他的題目有說不能用公式解耶>"<
→ spits:令n=2^k 代進去解  並不會很難解