บันทึกส่วนตัว: Asymptotic

Asymptotic แต่ละชนิด จะได้ดังนี้ คือ

Big-Oh ( $O$ )
$O(g(n)) = \{ f(n) | f(n) \preceq g(n) \}$
ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตต่ำกว่าหรือเท่ากับ g(n)

เช่น ถ้ากำหนดให้ $O(g(n)) = N^2$

ดังนั้น เซ็ตของคำตอบก็คือ $\{ N, \log N, N \log N, \frac{N^2}{2}, \dots \}$
Little-Oh ( $o$ )
$O(g(n)) = \{ f(n) | f(n) \prec g(n) \}$
ผลลัพธ์ที่ได้จะเหมือนกับ Big-Oh แต่จะต่างกันนิดเดียวคือ ฟังก์ชัน f(n) ต้องมีอัตราการเติบโตต่ำกว่าฟังก์ชัน g(n)
เช่น กำหนดให้ $o(g(n)) = N^2$
ดังนั้น $\frac{N^2}{2}$ จะไม่อยู่ในเซ็ตของคำตอบ เพราะมีอัตราการเติบโตเท่ากัน
Big-Omega ( $\Omega$ )
$O(g(n)) = \{ f(n) | f(n) \succeq g(n) \}$

ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่าหรือเท่ากับ g(n)
Little-Omega( $\omega$ )

$O(g(n)) = \{ f(n) | f(n) \succ g(n) \}$

ผลลัพธ์ที่ได้คือ เซ็ตของฟังก์ชันที่มีค่าอัตราการเติบโตสูงกว่า g(n)
Theta( $\Theta$ )
$O(g(n)) = \{ f(n) | f(n) \succeq \Omega(g(n)) \ \cap\ f(n) \preceq O(g(n)) \}$