Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.

a) T(n) = n + 2log n ≤ 3n với n ≥ 1. Vậy T(n) = O(n).

b) T(n) = n2 + 3nlogn +2n ≤ 6n với n ≥ 1. Vậy T(n) = O(n). 

c) T(n) = O(1), độ phức tạp hằng số.

d) T(n) = 2n+1 = 2.2" = O(2").

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

– Câu lệnh 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 − 1, nên vòng lặp có n – 1 bước lặp. 

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

• Hai lệnh gán tại dòng 4 và 5.

• Vòng lặp while tại dòng 6. Vòng lặp này sẽ chạy tối đa là i lần. Mỗi lần lặp chương trình sẽ thực hiện hai lệnh gán tại dòng 7 và 8, cần 2 đơn vị thời gian. • Lệnh gán tại dòng 9 cần 1 đơn vị thời gian.

Tổng hợp lại chương trình trên có thời gian chạy tối đa là: