bai 1
bai lam de tham khao ai lam roi post len cho cac ban xem 1 minh lam khong het
Code:
T(1)=1
T(n)=8T(n/2)+n
Taco
T(n)=8T(n/2)+n
=8^2T(n/2^2)+(2+1)n
=8^3T(n/2^3)+(2^4+2+1)n
.................
T(n)=8^i(n/2^i)+n(2^i-1/2-1)
ket thuc khi n/2^i=1<=>i=logn
T(n)=8^logn+n*2^logn-n
=n^3+n^2-n<=2n^3
vay T(n)=O(n^3)
bai lam de tham khao ai lam roi post len cho cac ban xem 1 minh lam khong het