`color(#FFFFFFff)(H)color(#E7E7E7ff)(o)color(#CFCFCFff)(r)color(#B7B7B7ff)(i)color(#9F9F9Fff)(z)color(#878787ff)(o)color(#6F6F6Fff)(n)`

Độ phức tạp của code: `O(n log n)`

Vòng lặp đầu tiên chạy `n / 2` lần. Bên trong vòng lặp, hàm pushdown có độ phức tạp là `O(log n)`

Vòng lặp thứ hai chạy `n - 1` lần. Bên trong vòng lặp, hàm swap có độ phức tạp là `O(1)` và hàm pushdown có độ phức tạp là `O(log n)`

Dộ phức tạp của hai vòng lặp là:

`=> n/2 * O(log n) + (n-1) * (O(1) + O(log n))` 
`=> O(n log n) + O(n) + O(n log n)` 
`=> O(n log n)`

`->` Độ phức tạp của code là `O(n log n)`

#danglam228

Vòng lặp này chạy từ n xuống 2.

Mỗi lần lặp, nó thực hiện hoán đổi (O(1)) và gọi pushdown (O(log n)).

Tổng độ phức tạp của giai đoạn này là O(n log n) vì:

Với mỗi lần lặp, ta thực hiện một hoán đổi O(1) và một lần gọi pushdown O(log n):

n×O(logn)=O(nlogn)

-> Tổng Độ Phức Tạp:  O(n)+O(nlogn)=O(nlogn)