bai 1

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 Very Happy