Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A

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 trạ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 có thời gian chạy tối đa là:

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

$T(n) = 3n – 2 + n(n – 1) = n^{2} + 2n – 2 = O(n^{2})$