สัญกรณ์Big Oเป็นสัญกรณ์ทางคณิตศาสตร์ที่อธิบายขนาดโดยประมาณของฟังก์ชันบนโดเมน Big O เป็นสมาชิกของกลุ่มสัญกรณ์ที่คิดค้นโดยนักคณิตศาสตร์ชาวเยอรมันPaul Bachmann ^{[ 1 ]}และEdmund Landau ^{[ 2 ]}และขยายโดยคนอื่นๆ ซึ่งเรียกรวมกันว่าสัญกรณ์ Bachmann–Landauตัวอักษร O ย่อมาจากOrdnungซึ่งหมาย ถึง ลำดับของการประมาณ

ในวิทยาการคอมพิวเตอร์สัญกรณ์ Big O ใช้ในการจำแนกอัลกอริทึมตามขนาดเวลาการทำงานหรือความต้องการพื้นที่^{[ a ]}ที่เพิ่มขึ้นตามอินพุต^{[ 3 ]}ในทฤษฎีจำนวนเชิงวิเคราะห์ สัญ กรณ์ Big O แสดงขอบเขตของการเติบโตของฟังก์ชันทางคณิตศาสตร์เช่น พจน์เศษเหลือในทฤษฎีบทจำนวนเฉพาะ [ ^{4 ] ใน} การวิเคราะห์ทางคณิตศาสตร์รวมถึงแคลคูลัส สัญกรณ์ Big O กำหนดขอบเขตของข้อผิดพลาดเมื่อตัดทอนอนุกรมกำลังและแสดงคุณภาพของการประมาณค่าฟังก์ชันค่าจริงหรือเชิงซ้อนด้วยฟังก์ชันที่ง่ายกว่า

โดยทั่วไป สัญกรณ์บิ๊กโอ (Big O notation) มักใช้เพื่ออธิบายฟังก์ชันตามอัตราการเติบโตเมื่อตัวแปรมีค่ามาก: ฟังก์ชันต่าง ๆ ที่มี อัตราการเติบโตเชิงเส้น กำกับ (asymptotic growth rate) เท่ากัน อาจแสดงด้วยสัญกรณ์โอเดียวกันได้ ตัวอักษรโอถูกใช้เพราะอัตราการเติบโตของฟังก์ชันเรียกอีกอย่างว่า อันดับของฟังก์ชันการอธิบายฟังก์ชันด้วยสัญกรณ์บิ๊กโอจะให้เพียงขอบเขตบนของอัตราการเติบโตของฟังก์ชัน เท่านั้น

สัญกรณ์ Big O เกี่ยวข้องกับสัญกรณ์อื่นๆ อีกหลายแบบ โดยใช้สัญลักษณ์, , , , , , , และเพื่ออธิบายขอบเขตประเภทอื่นๆ ของอัตราการเติบโต^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]}${\displaystyle o}$${\displaystyle \sim }$${\displaystyle \Omega }$${\displaystyle \ll }$${\displaystyle \gg }$${\displaystyle \asymp }$${\displaystyle \omega }$${\displaystyle \Theta }$

Bachmann เสนอสัญกรณ์นี้ในปี พ.ศ. 2337 และ Landau ขยายสัญกรณ์นี้ในปี พ.ศ. 2452 สัญกรณ์ก่อนหน้านี้ได้รับการเสนอโดยPaul du Bois-Reymondในปี พ.ศ. 2413 ^{[ 9 ]}

ให้ฟังก์ชันที่ต้องการประมาณค่าเป็น ฟังก์ชันค่า จริงหรือ ค่า เชิงซ้อนที่กำหนดบนโดเมนและให้ฟังก์ชันเปรียบเทียบเป็นฟังก์ชันค่าจริงที่ไม่เป็นลบที่กำหนดบนเซตเดียวกันตัวเลือกทั่วไปสำหรับโดเมน ได้แก่ ช่วงของจำนวนจริงที่มีขอบเขตหรือไม่มีขอบเขต เซตของจำนวนเต็มบวก เซตของจำนวนเชิงซ้อนและคู่ของจำนวนจริง/จำนวนเชิงซ้อน เมื่อเขียนโดเมนอย่างชัดเจนหรือเข้าใจโดยปริยาย เราสามารถเขียนได้ดังนี้ ${\textstyle f,}$${\textstyle D,}$${\textstyle g,}$${\textstyle D.}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\ }$$

ซึ่งอ่านว่า "${\textstyle f(x)}$มีขนาดใหญ่${\textstyle O}$กว่า" ถ้ามีจำนวนจริงบวกอยู่จำนวนหนึ่งซึ่งเป็นไปตามเงื่อนไขที่ว่า ${\textstyle g(x)}$${\textstyle M}$

$${\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ for\ all\ }}~\quad x\in D.}$$

ถ้า(เช่นgไม่เป็นศูนย์เลย) ตลอดทั้งโดเมนนิยามที่เทียบเท่ากันคือ อัตราส่วนนั้นมีขอบเขตกล่าวคือ มีจำนวนจริงบวกอยู่จำนวนหนึ่งที่ทำให้สำหรับทุก ๆสิ่งเหล่านี้ครอบคลุมการใช้งานทั้งหมดของbigในวิทยาศาสตร์คอมพิวเตอร์และคณิตศาสตร์ รวมถึงการใช้งานในกรณีที่โดเมนเป็นจำนวนจำกัด จำนวนอนันต์ จำนวนจริง จำนวนเชิงซ้อน ตัวแปรเดียว หรือหลายตัวแปร ในการใช้งานส่วนใหญ่ เรามักเลือกฟังก์ชันที่ปรากฏในอาร์กิวเมนต์ของให้มีรูปแบบที่เรียบง่ายที่สุดเท่าที่จะเป็นไปได้ โดยละเว้นปัจจัยคงที่และพจน์ลำดับต่ำกว่า จำนวนนี้เรียกว่าค่าคงที่โดยนัยเพราะโดยปกติแล้วจะไม่ระบุไว้ เมื่อใช้ สัญกรณ์ bigสิ่งสำคัญคือมีค่าจำกัดอยู่ ไม่ใช่ค่าเฉพาะของมัน สิ่งนี้ทำให้การนำเสนออสมการเชิงวิเคราะห์หลายอย่างง่ายขึ้น ${\displaystyle g(x)>0}$${\displaystyle D,}$${\textstyle {\frac {f(x)}{g(x)}}}$${\displaystyle M}$${\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}$${\displaystyle x\in D.}$${\textstyle O}$${\displaystyle g(x)}$${\textstyle O{\bigl (}\cdot {\bigr )}}$${\textstyle M}$${\textstyle O}$${\displaystyle M}$

สำหรับฟังก์ชันที่กำหนดบนจำนวนจริงบวกหรือจำนวนเต็มบวก คำจำกัดความที่เข้มงวดกว่าและขัดแย้งกันเล็กน้อยยังคงใช้กันทั่วไป^{[ 3 ] [ 10 ]}โดยเฉพาะในวิทยาศาสตร์คอมพิวเตอร์ เมื่อจำกัดเฉพาะฟังก์ชันที่เป็น บวก ในที่สุดสัญกรณ์

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {as}}\quad x\to \infty }$$

หมายความว่าสำหรับจำนวนจริงบางจำนวนในโดเมนในที่นี้ นิพจน์ไม่ได้บ่งชี้ถึงขีดจำกัดแต่หมายถึงแนวคิดที่ว่าความไม่เท่าเทียมกันเป็นจริงสำหรับค่าที่มากพอนิพจน์มักจะถูกละเว้น^{[ 3 ]}${\textstyle a,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$${\textstyle \left[a,\infty \right).}$${\textstyle x\to \infty }$${\textstyle x.}$${\textstyle x\to \infty }$

ในทำนองเดียวกัน สำหรับจำนวนจริงสัญลักษณ์ ${\textstyle a,}$

$${\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ as }}\ x\to a}$$

หมายความว่าสำหรับค่าคงที่บางค่าในช่วงนั้นซึ่งก็คือในบริเวณใกล้เคียงเล็กๆ ของ นอกจากนี้ สัญลักษณ์ ยัง หมายความว่านิพจน์ที่ซับซ้อนกว่านี้ก็เป็นไปได้เช่นกัน ${\textstyle c>0,}$${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$${\displaystyle \left[ac,a+c\right];}$${\displaystyle a.}$$${\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ }$$${\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}$

แม้จะมีเครื่องหมายเท่ากับ ( = ) ปรากฏอยู่ตามที่เขียนไว้ แต่สำนวนนี้ไม่ได้หมายถึงความเท่าเทียมกันแต่หมายถึงความไม่เท่าเทียมกันระหว่างและ${\textstyle f(x)=O{\bigl (}g(x){\bigr )}}$${\textstyle f}$${\textstyle g.}$

ในช่วงทศวรรษ 1930 ^{[ 6 ]}นักทฤษฎีจำนวนชาวรัสเซียIM Vinogradovได้นำเสนอสัญลักษณ์ซึ่งถูกนำมาใช้มากขึ้นในทฤษฎีจำนวน^{[ 4 ] [ 11 ] [ 12 ]}และสาขาอื่นๆ ของคณิตศาสตร์ เป็นทางเลือกแทนสัญลักษณ์ เรามี ${\displaystyle \ll ,}$${\textstyle O}$

$${\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}$$

บ่อยครั้งที่มีการใช้สัญลักษณ์ทั้งสองแบบในงานเขียนเดียวกัน

ในวิทยาการคอมพิวเตอร์^{[ 3 ]}เป็นเรื่องปกติที่จะกำหนดbig${\textstyle O}$ให้เป็นการกำหนดเซตของฟังก์ชันด้วยเช่นกัน เมื่อระบุฟังก์ชันบวก (หรือไม่ใช่ลบ) แล้ว จะตีความได้ว่าเป็นการแทนเซตของฟังก์ชันทั้งหมดที่ตรงตามเงื่อนไขจากนั้นสามารถเขียนได้เทียบเท่าว่า "ฟังก์ชันอยู่ในเซตของฟังก์ชันทั้งหมดที่มีลำดับไม่เกิน"${\displaystyle g(x)}$${\textstyle O{\bigl (}g(x){\bigr )}}$${\textstyle {\tilde {f}}}$${\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}.}$${\textstyle f(x)\in O{\bigl (}g(x){\bigr )},}$${\textstyle \ f(x)\ }$${\textstyle g(x).}$

โดยทั่วไปแล้วสัญลักษณ์นี้จะถูกนำไปใช้กับช่วงอนันต์ของจำนวนจริงและแสดงถึงพฤติกรรมของฟังก์ชันสำหรับค่าn ที่มาก ๆ ในบริบทนี้ ผลกระทบของพจน์ที่เติบโต "เร็วที่สุด" จะทำให้พจน์อื่น ๆ ไม่สำคัญในที่สุด ดังนั้นจึงสามารถใช้กฎการลดรูปต่อไปนี้ได้: ${\displaystyle O}$${\displaystyle [a,\infty )}$${\displaystyle x}$

• ถ้าเป็นผลรวมของหลายพจน์ หากมีพจน์ใดที่มีอัตราการเติบโตสูงสุด ก็สามารถเก็บไว้และตัดพจน์อื่นๆ ทิ้งได้${\displaystyle f(x)}$
• ถ้าเป็นผลคูณของตัวประกอบหลายตัว ค่าคงที่ใดๆ (ตัวประกอบในผลคูณที่ไม่ขึ้นอยู่กับ) สามารถละเว้นได้${\displaystyle f(x)}$${\displaystyle x}$

ตัวอย่างเช่น ให้และสมมติว่าเราต้องการทำให้ฟังก์ชันนี้ง่ายขึ้น โดยใช้สัญลักษณ์ เพื่ออธิบายอัตราการเติบโตสำหรับค่า ที่มากฟังก์ชันนี้เป็นผลรวมของสามพจน์ ได้แก่, และในบรรดาสามพจน์นี้ พจน์ที่มีอัตราการเติบโตสูงสุดคือพจน์ที่มีเลขชี้กำลังมากที่สุดเมื่อเทียบกับนั่นคือตอนนี้เราสามารถใช้กฎข้อที่สองได้: เป็นผลคูณของและโดยที่ตัวประกอบแรกไม่ขึ้นอยู่กับการละเว้นตัวประกอบนี้ทำให้ได้รูปแบบที่ง่ายขึ้นคือ ดังนั้น เราจึงกล่าวว่าเป็น "บิ๊กโอ" ของในทางคณิตศาสตร์ เราสามารถเขียนสำหรับทุกเราสามารถยืนยันการคำนวณนี้ได้โดยใช้คำนิยามอย่างเป็นทางการ: ให้และเมื่อใช้คำนิยามอย่างเป็นทางการจากข้างต้น ข้อความที่เทียบเท่ากับการขยายความ สำหรับค่าจำนวนจริงบวกที่เหมาะสมบางค่าและสำหรับทุกเพื่อพิสูจน์สิ่งนี้ ให้ดังนั้น สำหรับทุก: ดังนั้น ในขณะที่มันเป็นความจริงเช่นกัน ด้วยเหตุผลเดียวกันว่า แต่ เป็นการประมาณค่าฟังก์ชันที่ไม่แม่นยำนัก ในทางกลับกัน ข้อความดังกล่าวเป็นเท็จ เพราะคำดังกล่าวทำให้ ไม่มีขอบเขตจำกัด ${\displaystyle f(x)=6x^{4}-2x^{3}+5}$${\displaystyle O}$${\displaystyle x}$${\displaystyle 6x^{4}}$${\displaystyle -2x^{3}}$${\displaystyle 5}$${\displaystyle x}$${\displaystyle 6x^{4}}$${\displaystyle 6x^{4}}$${\displaystyle 6}$${\displaystyle x^{4}}$${\displaystyle x}$${\displaystyle x^{4}}$${\displaystyle f(x)}$${\displaystyle x^{4}}$${\displaystyle f(x)=O(x^{4})}$${\displaystyle x\geq 1}$${\displaystyle f(x)=6x^{4}-2x^{3}+5}$${\displaystyle g(x)=x^{4}}$${\displaystyle f(x)=O(x^{4})}$$${\displaystyle |f(x)|\leq Mx^{4}}$$${\displaystyle M}$${\displaystyle x\geq 1}$${\displaystyle M=13}$${\displaystyle x\geq 1}$$${\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|-2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}$$$${\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}$$${\displaystyle f(x)=O(x^{10})}$${\displaystyle f}$${\displaystyle f(x)=O(x^{3})}$${\displaystyle 6x^{4}}$${\displaystyle f(x)/x^{3}}$

เมื่อฟังก์ชันอธิบายจำนวนขั้นตอนที่จำเป็นในอัลกอริทึมที่มีอินพุตนิพจน์เช่น โดยที่โดเมนโดยนัยคือเซตของจำนวนเต็มบวก อาจถูกตีความได้ว่าอัลกอริทึมนั้นมีความซับซ้อนของเวลา อย่างมากที่สุดอยู่ในลำดับ${\displaystyle T(n)}$${\displaystyle n}$$${\displaystyle T(n)=O(n^{2})}$$${\displaystyle n^{2}}$

นอกจากนี้ ยังสามารถใช้ Big O เพื่ออธิบายพจน์ความคลาดเคลื่อนในการประมาณค่าฟังก์ชันทางคณิตศาสตร์ในช่วงจำกัดได้อีกด้วย พจน์ที่มีนัยสำคัญที่สุดจะถูกเขียนออกมาอย่างชัดเจน จากนั้นพจน์ที่มีนัยสำคัญน้อยที่สุดจะถูกสรุปไว้ในพจน์ Big O เดียว ตัวอย่างเช่น พิจารณาอนุกรมเลขชี้กำลังและนิพจน์สองแบบที่ใช้ได้เมื่อมีค่าเล็ก: นิพจน์ตรงกลาง(บรรทัดที่มี" " )หมายความว่าค่าสัมบูรณ์ของความคลาดเคลื่อน มีค่าอย่างมากที่สุดเท่ากับค่าคงที่บางค่าคูณเมื่อมีค่าเล็ก นี่เป็นตัวอย่างของการใช้ทฤษฎีบทของเทย์เลอร์ ${\displaystyle x}$$${\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ สำหรับ x ที่มีค่าจำกัดทั้งหมด\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ สำหรับ |x| ≤ 1 ทั้งหมด\\[4pt]&=1+x+O(x^{2})&&{\text{ สำหรับ |x| ≤ 1 ทั้งหมด.\end{aligned}}}$$${\displaystyle O(|x^{3}|)}$${\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }$${\displaystyle ~|x^{3}|\ }$${\displaystyle \ x~}$

พฤติกรรมของฟังก์ชันที่กำหนดอาจแตกต่างกันอย่างมากในโดเมนจำกัดเมื่อเทียบกับโดเมนอนันต์ ตัวอย่างเช่น ในขณะที่ $${\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ สำหรับ }}x\geq 1}$$$${\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ สำหรับ }}|x|\leq 1.}$$

$${\displaystyle x\sin y=O(x)\quad {\text{ สำหรับ }}x\geq 1,y{\text{ จำนวนจริงใดๆ}}}$$

$${\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}$$

$${\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}$$

$${\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}$$

ในที่นี้เรามี ฟังก์ชัน ตัวแปรเชิงซ้อนของตัวแปรสองตัว โดยทั่วไปแล้ว ฟังก์ชันที่มีขอบเขตใดๆ ก็ตามจะเป็นฟังก์ชันที่มีขอบเขต ${\displaystyle O(1)}$

$${\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}$$

ตัวอย่างสุดท้ายแสดงให้เห็นถึงการผสมผสานระหว่างโดเมนจำกัดและโดเมนอนันต์บนตัวแปรต่างๆ

ในตัวอย่างทั้งหมดนี้ ขอบเขตจะเป็นค่าเดียวกันในตัวแปรทั้งสอง บางครั้งในนิพจน์หลายตัวแปร ตัวแปรหนึ่งอาจมีความสำคัญมากกว่าตัวแปรอื่น และเราอาจแสดงว่าค่าคงที่โดยนัยขึ้นอยู่กับตัวแปรหนึ่งตัวหรือมากกว่านั้นโดยใช้ตัวห้อยกับสัญลักษณ์ O หรือสัญลักษณ์อื่น ตัวอย่างเช่น พิจารณานิพจน์ต่อไปนี้ ${\displaystyle M}$${\displaystyle \ll }$

$${\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}$$

นี่หมายความว่าสำหรับจำนวนจริงแต่ละจำนวนจะมีค่าคงที่ซึ่งขึ้นอยู่กับดังนั้นสำหรับทุกค่า ข้อความเฉพาะนี้ได้มาจาก ทฤษฎีบททวิ นาม ทั่วไป${\displaystyle b}$${\displaystyle M_{b}}$${\displaystyle b}$${\displaystyle 0\leq x\leq 1}$$${\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.}$$

อีกตัวอย่างหนึ่งที่พบได้ทั่วไปในทฤษฎีอนุกรมเทย์เลอร์คือ โดยค่าคงที่ที่แฝงอยู่จะขึ้นอยู่กับขนาดของโดเมน $${\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}}$$

หลักการใช้ตัวห้อยใช้กับสัญลักษณ์อื่นๆ ทั้งหมดในหน้านี้

${\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}$

${\displaystyle f\cdot O(g)=O(|f|g)}$

ถ้าเช่นนั้น... จึงสรุปได้ว่า ถ้าเช่นนั้น... ${\displaystyle f_{1}=O(g_{1})}$${\displaystyle f_{2}=O(g_{2})}$${\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}$${\displaystyle f_{1}=O(g)}$${\displaystyle f_{2}=O(g)}$${\displaystyle f_{1}+f_{2}=O(g)}$

ให้kเป็นค่าคงที่ที่ไม่เป็นศูนย์ ดังนั้น . กล่าวอีกนัยหนึ่ง ถ้าแล้ว${\displaystyle O(|k|\cdot g)=O(g)}$${\displaystyle f=O(g)}$${\displaystyle k\cdot f=O(g).}$

ถ้าเช่นนั้น ... ${\displaystyle f=O(g)}$${\displaystyle g=O(h)}$${\displaystyle f=O(h)}$

ถ้าฟังก์ชันของจำนวนเต็มบวก สามารถเขียนได้ในรูปผลรวมจำกัดของฟังก์ชันอื่น ๆ ฟังก์ชันที่เติบโตเร็วที่สุดจะเป็นตัวกำหนดลำดับของฟังก์ชันนั้นตัวอย่างเช่น ${\displaystyle f}$${\displaystyle n}$${\displaystyle f(n)}$

${\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}$

กฎทั่วไปบางประการเกี่ยวกับการเติบโตไปสู่อนันต์ ; คุณสมบัติข้อที่ 2 และ 3 ด้านล่างสามารถพิสูจน์ได้อย่างเคร่งครัดโดยใช้กฎของโลปิตาล :

สำหรับแล้ว เช่นนั้น ${\displaystyle b\geq a}$$${\displaystyle n^{a}=O(n^{b})}$$${\displaystyle n\to \infty }$

สำหรับค่าบวกใดๆ ไม่ว่าจะมีขนาดใหญ่หรือ เล็กเพียง ใด ในที่นี้ ค่าคงที่โดยนัยจะขึ้นอยู่กับทั้งและ${\displaystyle a,b,}$$${\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),}$$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$

สำหรับทุกสิ่งที่เป็นบวก ไม่ว่าจะใหญ่หรือเล็กแค่ไหน ก็ตาม ${\displaystyle a,b,}$$${\displaystyle n^{a}=O_{a,b}(e^{bn}),}$$${\displaystyle a}$${\displaystyle b}$

ฟังก์ชันที่เติบโตเร็วกว่าสำหรับค่าใดๆเรียกว่าซูเปอร์โพลินอมิอัล ส่วนฟังก์ชันที่เติบโตช้ากว่าฟังก์ชันเลขชี้กำลังใดๆ ในรูปแบบที่มีเรียกว่าซับเลขชี้กำลัง อัลกอริทึมบางอย่างอาจใช้เวลาที่ทั้งเป็นซูเปอร์โพลินอมิอัลและซับเลขชี้กำลังพร้อมกัน ตัวอย่างเช่น อัลกอริทึมที่เร็วที่สุดเท่า ที่ ทราบสำหรับการแยกตัวประกอบจำนวนเต็มและฟังก์ชัน${\displaystyle n^{c}}$${\displaystyle c}$${\displaystyle c^{n}}$${\displaystyle c>1}$${\displaystyle n^{\log n}}$

เราอาจละเว้นเลขยกกำลังใดๆภายในลอการิทึมได้ สำหรับค่าบวกใดๆสัญลักษณ์มีความหมายเหมือนกับเนื่องจากในทำนองเดียวกัน ลอการิทึมที่มีฐานคงที่ต่างกันจะเทียบเท่ากันในแง่ของสัญลักษณ์บิ๊กโอ ในทางกลับกัน เลขยกกำลังที่มีฐานต่างกันจะไม่เรียงลำดับเดียวกัน ตัวอย่างเช่นและจะไม่เรียงลำดับเดียวกัน ${\displaystyle n}$${\displaystyle c}$${\displaystyle O(\log n)}$${\displaystyle O(\log(n^{c}))}$${\displaystyle \log(n^{c})=c\log n}$${\displaystyle 2^{n}}$${\displaystyle 3^{n}}$

ในบริบทการใช้งานที่ซับซ้อนกว่านั้น คำว่า "คงที่" สามารถปรากฏในตำแหน่งต่างๆ ในสมการได้ แม้กระทั่งหลายครั้งในแต่ละด้าน ตัวอย่างเช่น ข้อความต่อไปนี้เป็นจริงสำหรับจำนวนเต็มบวก: ความหมายของข้อความดังกล่าวมีดังนี้: สำหรับ ฟังก์ชัน ใดๆที่สอดคล้องกับเงื่อนไขแต่ละข้อทางด้านซ้าย จะมี ฟังก์ชัน บางฟังก์ชันที่สอดคล้องกับเงื่อนไขแต่ละข้อทางด้านขวา ซึ่งเมื่อแทนฟังก์ชันทั้งหมดเหล่านี้ลงในสมการแล้วจะทำให้ทั้งสองข้างเท่ากัน ตัวอย่างเช่น สมการที่สามข้างต้นหมายความว่า: "สำหรับฟังก์ชันใดๆ ที่สอดคล้องกับเงื่อนไขจะมีฟังก์ชันบางฟังก์ชันที่ทำให้" ค่าคงที่โดยนัยในข้อความ " " อาจขึ้นอยู่กับค่าคงที่โดยนัยในนิพจน์ " " ${\displaystyle O(\cdot )}$${\displaystyle n}$$${\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}$$${\displaystyle O(\cdot )}$${\displaystyle O(\cdot )}$${\displaystyle f(n)=O(1)}$${\displaystyle g(n)=O(e^{n})}$${\displaystyle n^{f(n)}=g(n)}$${\displaystyle g(n)=O(e^{n})}$${\displaystyle f(n)=O(1)}$

ตัวอย่างเพิ่มเติม: $${\displaystyle {\begin{aligned}f=O(g)\;&\Rightarrow \;\int _{a}^{b}f=O{\bigg (}\int _{a}^{b}g{\bigg )}\\f(x)=g(x)+O(1)\;&\Rightarrow \;e^{f(x)}=O(e^{g(x)})\\(1+O(1/x))^{O(x)}&=O(1)\quad {\text{ for }}x>0\\\sin x&=O(|x|)\quad {\text{ for all real }}x.\end{aligned}}}$$

เมื่อฟังก์ชันทั้งสองเป็นบวก Vinogradov ^{[ 6 ]}ได้แนะนำสัญลักษณ์ซึ่งมีความหมายเหมือนกับสัญลักษณ์ทั้งสองของ Vinogradov มีความสมมาตรทางสายตา เช่นเดียวกับฟังก์ชันบวกเรา มี${\displaystyle f,g}$${\displaystyle f(x)\gg g(x)}$${\displaystyle g(x)=O(f(x))}$${\displaystyle f,g}$$${\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}$$

ในปี พ.ศ. 2519 Donald Knuth ^{[ 8 ]} ได้กำหนด

${\displaystyle f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))}$

ซึ่งมีความหมายเหมือนกับของวินอกราดอฟ ${\displaystyle f(x)\gg g(x)}$

อย่างไรก็ตาม ก่อนหน้านี้ Hardy และ Littlewood ^{[ 7 ]}ได้กำหนดนิยามที่แตกต่างออกไปและสัญลักษณ์ของพวกเขายังคงใช้กันอย่างแพร่หลายในทฤษฎีจำนวนเชิงวิเคราะห์ในปัจจุบัน^{[ 13 ] [ 11 ] [ 12 ]} Knuth ได้ให้เหตุผลในการใช้สัญลักษณ์เพื่ออธิบายคุณสมบัติที่แข็งแกร่งกว่า^{[ 8 ]}ว่า "สำหรับการใช้งานทั้งหมดที่ฉันได้เห็นมาจนถึงตอนนี้ในวิทยาศาสตร์คอมพิวเตอร์ ข้อกำหนดที่แข็งแกร่งกว่า ... นั้นเหมาะสมกว่ามาก" Knuth ยังเขียนเพิ่มเติมว่า "ถึงแม้ว่าฉันจะเปลี่ยนนิยามของ Hardy และ Littlewood ของ แต่ฉันรู้สึกว่ามีเหตุผลที่จะทำเช่นนั้น เพราะนิยามของพวกเขาไม่ได้ถูกนำมาใช้กันอย่างแพร่หลาย และเพราะมีวิธีอื่นที่จะพูดในสิ่งที่พวกเขาต้องการจะพูดในกรณีที่ค่อนข้างหายากเมื่อนิยามของพวกเขาใช้ได้" ^{[ 8 ]}สัญลักษณ์ขนาดใหญ่ของ Knuth ยังคงใช้กันอย่างแพร่หลายในวิทยาศาสตร์คอมพิวเตอร์และคณิตศาสตร์เชิงการจัดเรียงในปัจจุบัน ${\displaystyle \Omega }$${\displaystyle \Omega }$${\displaystyle \Omega }$${\displaystyle \Omega }$

ในทฤษฎีจำนวนเชิงวิเคราะห์^{[ 12 ]}สัญลักษณ์นี้หมายถึงทั้ง และสัญลักษณ์นี้เดิมทีเป็นของ Hardy ^{[ 5 ]}สัญลักษณ์ของ Knuth สำหรับแนวคิดเดียวกันคือ[ ^{8 ] โดย}คร่าวๆ ข้อความเหล่านี้ยืนยันว่าและมีลำดับเดียวกันสัญลักษณ์เหล่านี้หมายความว่ามีค่าคงที่บวก เพื่อให้ สำหรับทุกในโดเมนร่วมของ เมื่อฟังก์ชันถูกกำหนดบนจำนวนเต็มบวกหรือจำนวนจริงบวก เช่นเดียวกับบิ๊กโอ ผู้เขียนมักตีความข้อความ และว่าเป็นจริงสำหรับทุกค่า ที่มีขนาดใหญ่พอสมควรนั่นคือ สำหรับทุกค่าที่เกินจุดบางจุดบางครั้งสิ่งนี้จะระบุโดยการเพิ่มต่อท้ายข้อความ ตัวอย่างเช่น เป็นจริงสำหรับโดเมนแต่เป็นเท็จถ้าโดเมนเป็นจำนวนเต็มบวกทั้งหมด เนื่องจากฟังก์ชันเป็นศูนย์ที่ ${\displaystyle f(x)\asymp g(x)}$${\displaystyle f(x)=O(g(x))}$${\displaystyle g(x)=O(f(x))}$${\displaystyle f(x)=\Theta (g(x))}$${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle M,N}$$${\displaystyle Ng(x)\leq f(x)\leq Mg(x)}$$${\displaystyle x}$${\displaystyle f,g}$${\displaystyle f(x)=\Omega (g(x))}$${\displaystyle f(x)=\Theta (g(x))}$${\displaystyle x}$${\displaystyle x}$${\displaystyle x_{0}}$${\displaystyle x\to \infty }$$${\displaystyle 2n^{2}-10n=\Theta (n^{2})}$$${\displaystyle n\geq 6}$${\displaystyle n=5}$

$${\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}$$

$${\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}$$

สัญลักษณ์

$${\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,}$$ หมายความว่ามีค่าคงที่บวกค่าหนึ่งที่ทำให้ สำหรับทุกค่าในทางตรงกันข้าม หมายความว่ามีค่าคงที่บวกค่าหนึ่ง ที่ทำให้สำหรับทุกค่าและ หมายความว่ามีค่าคงที่บวกหลายค่าที่ ทำให้สำหรับทุกค่า ${\displaystyle M}$${\displaystyle f(n)\geq e^{Mn}}$${\displaystyle n\geq 1}$$${\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,}$$${\displaystyle M}$${\displaystyle f(n)\geq e^{-Mn}}$${\displaystyle n\geq 1}$$${\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,}$$${\displaystyle M,N}$${\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}$${\displaystyle n\geq 1}$

สำหรับโดเมนใดๆแต่ละ ข้อความจะเป็นสำหรับทุกสิ่งในนั้น ${\displaystyle D}$$${\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},}$$${\displaystyle x}$${\displaystyle D}$

ต่อไปนี้คือรายการของประเภทฟังก์ชันที่มักพบเห็นได้ทั่วไปเมื่อวิเคราะห์เวลาการทำงานของอัลกอริทึม ในแต่ละกรณีcเป็นค่าคงที่บวก และnเพิ่มขึ้นอย่างไม่มีขอบเขต โดยทั่วไปแล้วฟังก์ชันที่เติบโตช้ากว่าจะถูกแสดงไว้ก่อน

สัญกรณ์	ชื่อ	ตัวอย่าง
${\displaystyle O(1)}$	คงที่	การหาค่ามัธยฐานสำหรับอาร์เรย์ตัวเลขที่เรียงลำดับแล้ว การคำนวณ การ ใช้ ตารางค้นหาขนาดคงที่${\displaystyle (-1)^{n}}$
${\displaystyle O(\alpha (n))}$	ฟังก์ชัน Ackermann ผกผัน	ความซับซ้อนเฉลี่ยต่อการดำเนินการสำหรับโครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกัน
${\displaystyle O(\log \log n)}$	ลอการิทึมคู่	จำนวนครั้งเฉลี่ยของการเปรียบเทียบที่ใช้ในการค้นหารายการโดยใช้การค้นหาแบบแทรกสอดในอาร์เรย์ที่เรียงลำดับแล้วซึ่งกระจายอย่างสม่ำเสมอ
${\displaystyle O(\log n)}$	ลอการิทึม	การค้นหารายการในอาร์เรย์ที่เรียงลำดับแล้วโดยใช้การค้นหาแบบไบนารี หรือ ต้นไม้ค้นหาแบบสมดุลตลอดจนการดำเนินการทั้งหมดในฮีปแบบไบโนเมียล
${\displaystyle O((\log n)^{c})}$${\textstyle c>1}$	โพลีลอการิทมิก	การเรียงลำดับเมทริกซ์แบบลูกโซ่สามารถแก้ไขได้ในเวลาแบบพหุลอการิทึมบนเครื่องเข้าถึงแบบสุ่มขนาน
${\displaystyle O(n^{c})}$${\textstyle 0<c<1}$	กำลังเศษส่วน	การค้นหาในต้นไม้ kd การทดสอบความเป็นจำนวนเฉพาะแบบง่าย โดยการหารทดลอง ( ) ${\displaystyle O({\sqrt {n}})}$
${\displaystyle O(n)}$	เชิงเส้น	การค้นหารายการในรายการที่ไม่เรียงลำดับหรือในอาร์เรย์ที่ไม่เรียงลำดับ การบวก จำนวนเต็ม nบิตสองจำนวนโดยใช้การทดแบบระลอกคลื่น
${\displaystyle O(n\log ^{*}n)}$	n log-star n	ดำเนินการสร้างสามเหลี่ยมของรูปหลายเหลี่ยมอย่างง่ายโดยใช้อัลกอริทึมของ Seidel [ 14 ]โดยที่${\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}$
${\displaystyle O(n\log n)=O(\log n!)}$	แบบลิเนียร์ลิเธียม , แบบลอการิธึมลิเธียม, แบบกึ่งลิเธียม หรือ"${\displaystyle n\log n}$	การแปลงฟูริเยร์แบบเร็ว (Fast Fourier Transform) ; การเรียงลำดับแบบเปรียบเทียบ ที่เร็วที่สุดเท่าที่จะเป็นไปได้ ; การเรียงลำดับ แบบฮีปซอร์ตและการเรียงลำดับแบบผสาน (Merge Sort)
${\displaystyle O(n^{2})}$	กำลังสอง	การคูณเลขสองหลักด้วยวิธีการคูณแบบพื้นฐานในตำราเรียน ; อัลกอริทึมการเรียงลำดับแบบง่ายๆ เช่น บับเบิลซอร์ต (bubble sort) , ซีเลคชันซอ ร์ต (selection sort ) และ อินเสิร์ชัน ซอร์ต (insertion sort ); ขอบเขต (กรณีที่เลวร้ายที่สุด) ของอัลกอริทึมการเรียงลำดับที่เร็วกว่าบางอย่าง เช่นควิกซอร์ต (quicksort) , เชลล์ซอร์ต (Shellsort)และทรีซอร์ต (tree sort)${\displaystyle n}$
${\displaystyle O(n^{c})}$	พหุนามหรือพีชคณิต	การวิเคราะห์ ไวยากรณ์แบบเชื่อมต่อต้นไม้ ; การจับคู่สูงสุดสำหรับกราฟสองส่วน ; การหาดีเทอร์มิแนนต์ด้วยการแยกส่วน LU
${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$${\textstyle 0<\alpha <1}$	สัญกรณ์ Lหรือเลขชี้กำลังย่อย	การแยกตัวประกอบของจำนวนโดยใช้ตะแกรงกำลังสองหรือตะแกรงสนามจำนวน
${\displaystyle O(c^{n})}$${\textstyle c>1}$	เลขชี้กำลัง	การหาคำตอบ (ที่แน่นอน) ของปัญหาพนักงานขายเดินทางโดยใช้การเขียนโปรแกรมเชิงพลวัตการตรวจสอบว่าข้อความตรรกะสองข้อความนั้นเทียบเท่ากันหรือไม่โดยใช้การค้นหาแบบบรูทฟอร์ซ
${\displaystyle O(n!)}$	แฟกทอเรียล	การแก้ปัญหาพนักงานขายเดินทางโดยใช้การค้นหาแบบบรูทฟอร์ซ การสร้างการเรียงสับเปลี่ยนแบบไม่จำกัดทั้งหมด ของ เซต ลำดับบางส่วน การหาดีเทอร์มิแนนต์ด้วยการกระจายลาปลาสการแจงนับพาร์ติชันทั้งหมดของเซต

บางครั้ง ข้อความดังกล่าวจะถูกลดทอนลงเพื่อให้ได้สูตรที่ง่ายกว่าสำหรับความซับซ้อนเชิงอะซิมโทติก ในตัวอย่างเหล่านี้จำนวนมาก เวลาในการทำงานจริงคือซึ่งสื่อถึงความแม่นยำที่มากกว่า ${\displaystyle f(n)=O(n!)}$${\displaystyle f(n)=O\left(n^{n}\right)}$${\displaystyle \Theta (g(n))}$

สำหรับฟังก์ชันค่าจริงหรือค่าเชิงซ้อนของตัวแปรจริง ที่มีสำหรับค่าที่มากพอ จะเขียนได้ว่า ^{[ 2 ]}${\displaystyle x}$${\displaystyle g(x)>0}$${\displaystyle x}$

${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }$

ถ้า นั่นคือ สำหรับค่าคงที่บวกε ทุกค่า จะมีค่าคงที่อยู่ค่าหนึ่งเช่นนั้น $${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.}$$${\displaystyle x_{0}}$

${\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}$

โดยสัญชาตญาณแล้ว นี่หมายความว่าเติบโตเร็วกว่ามากหรือกล่าวอีกนัยหนึ่งคือเติบโตช้ากว่ามาก ตัวอย่างเช่น มี ${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle g(x)}$

${\displaystyle 200x=o(x^{2})}$และ     ทั้งสองอย่างเช่น${\displaystyle 1/x=o(1),}$${\displaystyle x\to \infty .}$

เมื่อเราสนใจพฤติกรรมของฟังก์ชันสำหรับค่าขนาดใหญ่ของ n การใช้สัญลักษณ์ little-o จะให้ข้อความที่ชัดเจนกว่าการใช้สัญลักษณ์ big-o ที่สอดคล้องกัน กล่าวคือ ทุกฟังก์ชันที่เป็น little-o ของ n ก็จะเป็น big-o ของ n ในช่วงใดช่วงหนึ่งแต่ไม่ใช่ทุกฟังก์ชันที่เป็น big-o ของ n จะเป็น little-o ของn ตัวอย่างเช่นแต่สำหรับn > 0${\displaystyle x}$${\displaystyle g}$${\displaystyle g}$${\displaystyle [a,\infty )}$${\displaystyle g}$${\displaystyle g}$${\displaystyle 2x^{2}=O(x^{2})}$${\displaystyle 2x^{2}\neq o(x^{2})}$${\displaystyle x\geq 1}$

Little-o รองรับการดำเนินการทางคณิตศาสตร์หลายอย่าง ตัวอย่างเช่น

ถ้าเป็นค่าคงที่ที่ไม่ใช่ศูนย์แล้วและ${\displaystyle c}$${\displaystyle f=o(g)}$${\displaystyle c\cdot f=o(g)}$

ถ้าเช่นนั้น${\displaystyle f=o(F)}$${\displaystyle g=o(G)}$${\displaystyle f\cdot g=o(F\cdot G).}$

ถ้าเช่นนั้น${\displaystyle f=o(F)}$${\displaystyle g=o(G)}$${\displaystyle f+g=o(F+G)}$

นอกจากนี้ยังสอดคล้องกับ ความสัมพันธ์ แบบถ่ายทอดได้ อีกด้วย :

ถ้าเช่นนั้น${\displaystyle f=o(g)}$${\displaystyle g=o(h)}$${\displaystyle f=o(h).}$

Little-o ยังสามารถขยายไปสู่กรณีจำกัดได้อีกด้วย: ^{[ 2 ]} ถ้า กล่าวอีกนัยหนึ่ง คือ สำหรับบางค่าที่ มี${\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}$$${\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.}$$${\displaystyle f(x)=\alpha (x)g(x)}$${\displaystyle \alpha (x)}$${\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}$

คำจำกัดความนี้มีประโยชน์อย่างยิ่งในการคำนวณลิมิตโดยใช้ชุดอนุกรมเทย์เลอร์ตัวอย่างเช่น:

${\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}$, ดังนั้น${\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}$

ความสัมพันธ์ที่เกี่ยวข้องกับ little-o คือสัญกรณ์ เชิงอะซิม โทติก สำหรับฟังก์ชันค่าจริงนิพจน์นี้ หมายถึง เราสามารถเชื่อมโยงสิ่งนี้กับ little-o ได้โดยสังเกตว่า ก็เทียบเท่ากับ เช่น กัน ในที่นี้หมายถึงฟังก์ชันที่เข้าใกล้ศูนย์เมื่อ เราอ่านสิ่งนี้ว่า " เป็นเชิงอะซิมโทติกของ " สำหรับฟังก์ชันที่ไม่เป็นศูนย์บนโดเมนเดียวกัน (จำกัดหรืออนันต์) ก่อให้เกิด ความ สัมพันธ์สมมูล${\displaystyle \sim }$${\displaystyle f,g}$$${\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty }$$$${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.}$$${\displaystyle f(x)\sim g(x)}$${\displaystyle f(x)=(1+o(1))g(x)}$${\displaystyle o(1)}$${\displaystyle x\to \infty }$${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle \sim }$

หนึ่งในทฤษฎีบทที่มีชื่อเสียงที่สุดที่ใช้สัญลักษณ์นี้ คือสูตรของสเตอร์ลิง ในทฤษฎีจำนวน ทฤษฎีบทจำนวนเฉพาะ ที่มีชื่อเสียง กล่าวว่า โดยที่คือจำนวนของจำนวนเฉพาะที่มีค่าไม่เกินและ คือลอการิทึม ธรรมชาติของ${\displaystyle \sim }$$${\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .}$$$${\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,}$$${\displaystyle \pi (x)}$${\displaystyle x}$${\displaystyle \log }$${\displaystyle x}$

เช่นเดียวกับ little-o ก็มีเวอร์ชันที่มีขอบเขตจำกัด (แบบสองด้านหรือแบบด้านเดียว ) ด้วยเช่นกัน ตัวอย่างเช่น $${\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}$$

ตัวอย่างเพิ่มเติม: ค่าเชิงเส้นกำกับสุดท้ายเป็นคุณสมบัติพื้นฐานของ ฟังก์ชันซีตาของรีมันน์ $${\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,}$$$${\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).}$$$${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (s\to 1^{+}).}$$

สำหรับฟังก์ชันที่มีค่าเป็นบวกและเป็นจริงในที่สุดสัญลักษณ์นี้ หมายถึง กล่าวอีกนัยหนึ่งคือโดยคร่าวๆ แล้วหมายความว่าเติบโต เร็วกว่า มาก${\displaystyle f,g,}$$${\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty }$$$${\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .}$$${\displaystyle g(x)=o(f(x))}$${\displaystyle f(x)}$${\displaystyle g(x)}$

ในปี พ.ศ. 2457 GH HardyและJE Littlewoodได้นำเสนอสัญลักษณ์ใหม่^{[ 7 ]}ซึ่งกำหนดไว้ดังนี้: ${\displaystyle \ \Omega ,}$

${\displaystyle f(x)=\Omega (g(x))\quad }$ราวกับว่า${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}$

ดังนั้น จึงเป็นการปฏิเสธของ${\displaystyle ~f(x)=\Omega (g(x))~}$${\displaystyle ~f(x)=o(g(x))~.}$

เมื่อปี พ.ศ. 2459 ผู้เขียนกลุ่มเดียวกันนี้ได้แนะนำสัญลักษณ์ใหม่สองตัวและกำหนดความหมายดังนี้: ^{[ 15 ]}${\displaystyle \ \Omega _{R}\ }$${\displaystyle \ \Omega _{L}\ ,}$

${\displaystyle f(x)=\Omega _{R}(g(x))\quad }$ราวกับว่า${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}$

${\displaystyle f(x)=\Omega _{L}(g(x))\quad }$ราวกับว่า${\displaystyle \quad x\to \infty \quad }$${\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}$

สัญลักษณ์เหล่านี้ถูกใช้โดยE. Landauโดยมีความหมายเดียวกันในปี พ.ศ. 2467 ^{[ 16 ]}อย่างไรก็ตาม ผู้เขียนที่ตามหลัง Landau ใช้สัญลักษณ์ที่แตกต่างกันสำหรับคำจำกัดความเดียวกัน: ^{[ 11 ]}สัญลักษณ์ดังกล่าวถูกแทนที่ด้วยสัญลักษณ์ปัจจุบันที่มีคำจำกัดความเดียวกัน และกลายเป็น${\displaystyle \ \Omega _{R}\ }$${\displaystyle \ \Omega _{+}\ }$${\displaystyle \ \Omega _{L}\ }$${\displaystyle \ \Omega _{-}~.}$

สัญลักษณ์ทั้งสามนี้รวมถึง(ซึ่งหมายความว่าและเป็นไปตามเงื่อนไขทั้งคู่) ปัจจุบันถูกนำมาใช้ในทฤษฎีจำนวนเชิงวิเคราะห์^{[ 11 ] [ 12 ]}${\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}$${\displaystyle \ f(x)=\Omega _{\pm }(g(x))\ }$${\displaystyle \ f(x)=\Omega _{+}(g(x))\ }$${\displaystyle \ f(x)=\Omega _{-}(g(x))\ }$

เรามี

${\displaystyle \sin x=\Omega (1)\quad }$เช่น${\displaystyle \quad x\to \infty \ ,}$

และแม่นยำยิ่งขึ้นไปอีก

${\displaystyle \sin x=\Omega _{\pm }(1)\quad }$เช่น${\displaystyle \quad x\to \infty ,~}$

โดยที่หมายความว่าด้านซ้ายเป็นทั้ง และ${\displaystyle \Omega _{\pm }}$${\displaystyle \Omega _{+}(1)}$${\displaystyle \Omega _{-}(1)}$

เรามี

${\displaystyle 1+\sin x=\Omega (1)\quad }$เช่น${\displaystyle \quad x\to \infty \ ,}$

และแม่นยำยิ่งขึ้นไปอีก

${\displaystyle 1+\sin x=\Omega _{+}(1)\quad }$เช่น${\displaystyle \quad x\to \infty \ ;}$

อย่างไรก็ตาม

${\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }$เช่น${\displaystyle \quad x\to \infty ~.}$

เพื่อทำความเข้าใจนิยามอย่างเป็นทางการ โปรดดู รายการสัญลักษณ์ตรรกศาสตร์ที่ใช้ในคณิตศาสตร์

สัญกรณ์	ชื่อ[ 8 ]	คำอธิบาย	คำจำกัดความอย่างเป็นทางการ	คำจำกัดความโดยย่อ [ 4 ] [ 5 ] [ 8 ] [ 7 ] [ 17 ] [ 18 ]
${\displaystyle f(n)=O(g(n))}$หรือ ${\displaystyle f(n)\ll g(n)}$(สัญกรณ์ของวินอกราดอฟ)	บิ๊กโอ; บิ๊กโอ; บิ๊กโอไมครอน[ 8 ] [ b ]	${\displaystyle |f|}$มีค่าสูงสุดจำกัดโดยg (โดยมีค่าคงที่ประกอบ) ${\displaystyle k}$	${\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty }$
${\displaystyle f(n)=o(g(n))}$	โอเล็ก โอเล็ก โอเล็ก โอเล็ก	fถูกครอบงำโดยgในเชิงอะซิมโทติก (สำหรับค่าคงที่ใดๆ) ${\displaystyle k}$	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}$	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}$
${\displaystyle f(n)=\Omega (g(n))}$	โอเมกาใหญ่ในทฤษฎีจำนวน (ฮาร์ดี้-ลิตเติลวูด)	${\displaystyle |f|}$ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {|f(n)|}{g(n)}}>0}$
${\displaystyle f(n)=\Omega _{+}(g(n))}$	โอเมก้าพลัส (ฮาร์ดี้-ลิตเติลวูด)	${\displaystyle f}$ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon f(n)\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\Omega _{-}(g(n))}$	โอเมก้าลบ (ฮาร์ดี้-ลิตเติลวูด)	${\displaystyle -f}$ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก	${\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon -f(n)\geq k\,g(n)}$	${\displaystyle \limsup _{n\to \infty }{\frac {-f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\Omega _{\pm }(g(n))}$	โอเมก้าพลัสและลบ	ทั้ง nor ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก ${\displaystyle f}$${\displaystyle -f}$	${\displaystyle f(n)=\Omega _{+}(g(n))}$และ${\displaystyle f(n)=\Omega _{-}(g(n))}$
${\displaystyle f(n)\asymp g(n)}$(สัญกรณ์ของฮาร์ดี้) หรือ(สัญกรณ์ของคนูธ) ${\displaystyle f(n)=\Theta (g(n))}$	อยู่ในลำดับเดียวกันกับ (ฮาร์ดี้); บิ๊กเธต้า (คนุธ)	fถูกจำกัดโดยgทั้งด้านบน (ด้วยตัวประกอบคงที่) และด้านล่าง (ด้วยตัวประกอบคงที่) ${\displaystyle k_{2}}$${\displaystyle k_{1}}$	${\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon }$${\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}$	${\displaystyle f(n)=O(g(n))}$และ${\displaystyle g(n)=O(f(n))}$
${\displaystyle f(n)\sim g(n)}$เนื่องจาก โดยที่มีค่าจำกัด${\displaystyle n\to a}$${\displaystyle a}$${\displaystyle \infty }$ หรือ${\displaystyle -\infty }$	ความสมมูลเชิงอะซิมโทติก	fเท่ากับg ในเชิงอะซิมโทติก	${\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }$(ในกรณีนี้) ${\displaystyle a=\infty }$	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1}$
${\displaystyle f(n)=\Omega (g(n))}$(สัญกรณ์ของ Knuth) หรือ ${\displaystyle f(n)\gg g(n)}$(สัญกรณ์ของวินอกราดอฟ)	โอเมก้าตัวใหญ่ในทฤษฎีความซับซ้อน (Knuth)	fมีขอบเขตล่างโดยgโดยมีค่าคงที่ประกอบอยู่ด้วย	${\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)}$	${\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0}$
${\displaystyle f(n)=\omega (g(n))}$เช่น, ${\displaystyle n\to a}$ ซึ่งอาจมีค่าจำกัดหรือ${\displaystyle a}$${\displaystyle \infty }$${\displaystyle -\infty }$	โอเมก้าขนาดเล็ก; โอเมก้าน้อย	fครอบงำgในเชิงอะซิมโทติก	${\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}$(สำหรับ) ${\displaystyle a=\infty }$	${\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty }$