2 vòng lặp lồng nhau độ phức tạp là O(n^2)?

[Lag_Lac (Lag /Lác)]

mọi người ơi, cho mình hỏi cách làm câu này với, mình tưởng độ phức tạp tồi nhất của nó là O(n^2) vì nó có 2 vòng lặp lồng nhau chứ. Nhưng kết quả đúng lại là O(n). Giải thích giúp mình với, mình cảm ơn nhiều

[nguyenchiemminhvu (NCMV)]

giả sử mảng a đã được sắp xếp giảm dần, vòng lặp while được thực hiện n lần, lúc đó k > n, những lần lặp tiếp theo của vòng for sẽ không chạy khối lệnh trong vòng lặp while nữa.

[Lag_Lac (Lag /Lác)]

người ta nói là xét trường hợp tồi nhất mà bạn. Vậy ý bạn là khi mảng a sắp xếp giảm dần thì là trường hợp tồi nhất, tại sao lại vậy nhỉ…Bạn có thể giải thích dõ hơn được ko

[Stanley00 (Stanley)]

k ban đầu bằng 1, bên trong vòng lặp, k được tăng 1 cho đến khi k>n => k=k+1 chỉ được thực hiện tối đa n lần => độ phức tạp cũng chỉ là O(n).