前一個(gè)：
T(n)=4T(n/2)+n可以等價(jià)地寫成T(2^t)=4T(2^(t-1))+2^t,
所以
T(2^t)+2^t=4T(2^(t-1))+2*2^t=4T(2^(t-1))+4*2^(t-1)=4[T(2^(t-1))+2^(t-1)],
令R(t)=T(2^t)+2^t,則上式說(shuō)明R(t)=4R(t-1).所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0),
所以
T(2^t)=R(t)-2^t=(4^t)R(0)-2^t=(4^t)[T(2^0)+2^0]-2^t=(4^t)[T(1)+1]-2^t=(4^t)T(1)+4^t-2^t,
或者寫成
T(n)=(n^2)T(1)+n^2-n,
其中T(1)可取任意常數(shù)
后一個(gè)：
T(n)=4T(n/2)+n^2可以等價(jià)地寫成T(2^t)=4T(2^(t-1))+4^t,
所以
T(2^t)-t*4^t=4T(2^(t-1))+4^t-t*4^t=4T(2^(t-1))-(t-1)*4^t=4[T(2^(t-1))-(t-1)*4^(t-1)],
令R(t)=T(2^t)-t*4^t,則上式說(shuō)明R(t)=4R(t-1).所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0),
所以
T(2^t)=R(t)+t*4^t=(4^t)R(0)+t*4^t=(4^t)[T(2^0)-0*2^0]+t*4^t=(4^t)T(1)+t*4^t,
或者寫成
T(n)=(n^2)T(1)+(n^2)ln(n)/ln(2),
其中T(1)可取任意常數(shù)