Xác định độ phức tạp thời gian của hàm sau:

Gọi T(n) là thời gian thực hiện của chương trình. Thời gian chạy của thuật toán được phân tích như sau:

- Lệnh gán tại dòng 2 cần 1 đơn vị thời gian

- Vòng lặp for tại dòng 3, biến i chạy từ 1 đến n, nên vòng lặp có n bước lặp

- Với mỗi bước lặp trên, chương trình thực hiện:

• Vòng lặp tại dòng 4, biến j chạy từ 1 đến i, nên vòng lặp thực hiện i bước lặp

• Với mỗi bước lặp:

• Chương trình thực hiện vòng lặp tại dòng 5, biến k chạy từ j đến j + i, vòng lặp có i + 1 bước lặp.

• Với mỗi bước lặp chương trình thực hiện 1 lệnh gán tại dòng 6 cần 1 đơn vị thời gian

- Lệnh trả về tại dòng 7 cần 1 đơn vị thời gian

Tổng hợp lại, hàm trên có thời gian chạy là:

$T(n)=2+\sum_{i=1}^{n}\sum_{j=1}^{i}(i+1)=2+\sum_{i=1}^{n}(i^{2}+i)=2\sum_{i=1}^{n}(i^{2})+\sum_{i=1}^{n}(i)$

$T(n)=2+\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}=2+\frac{n^{3}+3n^{2}+2n}{3}$

Suy ra $T(n)=O(n^{3})$