Big O trong toán rời rạc (Discrete Math)

[GaMatOng]

Em đã google trước khi hỏi nhưng em chưa hiểu chỗ này lắm ạ

Giả sử viết

3x^2 + 2x + 2 = O(x^2)

Điều này có nghĩa là gì ạ, có phải là độ phức tạp của 3x^2 + 2x + 2 khi x tiến ra vô cùng giống độ phức tạp của x^2 không ạ?

[rogp10]

Dịch từng chữ O(x^2) thực chất là một tập hợp các hàm “nhỏ hơn hoặc bằng” x^2, nên viết = là không đúng, nhưng nếu viết dấu “thuộc” thì công thức sẽ phức tạp hơn (Taylor )
Hay nói cách khác, 3x^2 + 2x + 2 “không quá cỡ” so với x^2 (big-theta là cùng một cỡ).

Big-O có một định nghĩa tương đương: f(n) = O(g(n)) <=> lim sup |f(n) / g(n)| < +inf.

• “sup” là để sin(n) = O(1).
• Ngoài ra lim sup f(n) := lim (sup [n..+inf].f) (biên trên, không phải max), mà sup(sin(n)) <= 1 (không nói == được ngay đâu ) nên sin(n) = O(1).