Thắc mắc cách tính Big-O

[gutsT (Kojiro)]

Chào mọi người,
Cho em hỏi bài này big-O là O(n^3) hay O(n^2) vậy ạ?
Theo cách tính của em là dòng 2 là O(n) còn dòng 3 là O(n*(n+1)/2) = O(n^2) thì Big-O của bài là O(n)*O(n^2) = O(n^3) đúng không ạ? Tại em có coi một số video thì người ta ra big-O là O(n^2) nên em không biết đúng hay sai
Do em mới học được 1 buổi ctdl&gt nên chưa hiểu lắm

Em cảm ơn

[HR16 (Gà Coder)]

Dòng thứ 3 chỉ lặp từ 1 đến 9 nên độ phức tạp của thuật toán này là: O(n^2 * 8) = O(n^2) (quy tắc bỏ hằng số)

Nếu dòng thứ 3 lặp đến j thì sẽ ra O(n^3)

[rogp10]

Dòng 1 và 2 đều là O(n) nên theo quy tắc nhân là O(n^2).

Vòng lặp biến k lặp 9 lần nên T(n) = 9 \cdot O(1) \cdot O(n^2) = O(n^2).

[gutsT (Kojiro)]

À hình như em hiểu sai vấn đề rồi, vòng lặp biến j lúc đầu em tính theo tổng cấp số cộng do j=i+1 nên mới ra là O(n*(n+1)/2) = O(n^2) gồm luôn cả vòng lặp biến i, còn vòng lặp của biến k do chỉ lặp đến 9 thôi nên sẽ là O(1). Kết quả cuối cùng là O(n^2)
Em cảm ơn ạ ^^