Câu hỏi về độ phức tạp của thuật toán lý thuyết

[Trung_Hieu_Vu1 (Trung Hiếu Vũ)]

anh chị cho em hỏi tại sao T(n) = O(n) cũng có thể nói là T(n) = O(n^2) vậy ạ, em đọc mà thấy hơi khó hiểu ạ

[rogp10]

Vì O(n) \subset O(n^2) mà

f(n) \in O(n) \overset{\text{định nghĩa}}{\iff}\ \exists n_0\exists C>0, |f(n)| \leq Cn, \forall n \geq n_0

Ta chọn n_1 = max(1, n_0), với n\geq n_1 \geq 1 thì |f(n)| \cdot 1 \leq C\cdot n \cdot n = C \cdot n^2, suy ra f(n) \in O(n^2).

Cuối cùng ta c/m O(n) \neq O(n^2):
Phủ định:
f(n) \not\in O(n) \iff \forall n_0\forall C>0\ \exists n\geq n_0, |f(n)| > Cn
mà \forall n_0 > C, n_0^2 > Cn_0 nên n^2 \not\in O(n)\ \Box