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 chương trình đượ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 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:

a 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 + vòng lặp có i + 1 bước lặp.

a 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à

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

Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?