ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีความซับซ้อนเชิงเวลาคือความซับซ้อนในการคำนวณที่อธิบายถึงปริมาณเวลาของคอมพิวเตอร์ที่ใช้ในการทำงานของอัลกอริทึมโดยทั่วไปแล้ว ความซับซ้อนเชิงเวลาจะถูกประมาณโดยการนับจำนวนการดำเนินการพื้นฐานที่อัลกอริทึมดำเนินการ โดยสมมติว่าการดำเนินการพื้นฐานแต่ละครั้งใช้เวลาคงที่ ดังนั้น ปริมาณเวลาที่ใช้และจำนวนการดำเนินการพื้นฐานที่อัลกอริทึมดำเนินการจึงถือว่ามีความสัมพันธ์กันด้วยปัจจัยคงที่

เนื่องจากเวลาในการทำงานของอัลกอริทึมอาจแตกต่างกันไปตามอินพุตที่มีขนาดเท่ากัน โดยทั่วไปจึงมักพิจารณาความซับซ้อนของเวลาในกรณีที่เลวร้ายที่สุดซึ่งเป็นปริมาณเวลาสูงสุดที่จำเป็นสำหรับอินพุตที่มีขนาดที่กำหนดส่วนความซับซ้อนในกรณีเฉลี่ย ซึ่งมักระบุไว้อย่างชัดเจนนั้น ไม่ค่อยพบเห็น และมักมีการระบุไว้อย่างชัดเจน ซึ่งเป็นค่าเฉลี่ยของเวลาที่ใช้กับอินพุตที่มีขนาดที่กำหนด (ซึ่งสมเหตุสมผลเพราะมีเพียงจำนวนจำกัดของอินพุตที่เป็นไปได้ที่มีขนาดที่กำหนด) ในทั้งสองกรณี ความซับซ้อนของเวลาโดยทั่วไปจะแสดงเป็นฟังก์ชันของขนาดของอินพุต^{[ 1 ] : 226} เนื่องจากโดยทั่วไปแล้วฟังก์ชันนี้คำนวณได้ยากอย่างแม่นยำ และเวลาในการทำงานสำหรับอินพุตขนาดเล็กมักไม่สำคัญ จึงมักมุ่งเน้นไปที่พฤติกรรมของความซับซ้อนเมื่อขนาดของอินพุตเพิ่มขึ้น นั่นคือพฤติกรรมเชิงอะซิมโทติกของความซับซ้อน ดังนั้น ความซับซ้อนของเวลาจึงมักแสดงโดยใช้สัญกรณ์บิ๊กโอโดยทั่วไปคือ, , , ,เป็นต้น โดยที่nคือขนาดในหน่วยบิตที่จำเป็นในการแสดงอินพุต ${\displaystyle O(n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle O(2^{n})}$

ความซับซ้อนของอัลกอริทึมถูกจำแนกตามประเภทของฟังก์ชันที่ปรากฏในสัญกรณ์บิ๊กโอ ตัวอย่างเช่น อัลกอริทึมที่มีความซับซ้อนด้านเวลา n คืออัลกอริทึมเวลาเชิงเส้นและอัลกอริทึมที่มีความซับซ้อนด้านเวลา n สำหรับค่าคงที่บางค่าคืออัลกอริทึมเวลาพหุนาม ${\displaystyle O(n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle \alpha >0}$

ตารางต่อไปนี้สรุปคลาสของความซับซ้อนของเวลาที่พบได้ทั่วไปบางคลาส ในตารางpoly( x ) = x ^{O (1)}กล่าว คือ พหุนามใน  x

ชื่อ	คลาสความซับซ้อน	ความซับซ้อนเชิงเวลา( O ( n ) )	ตัวอย่างระยะเวลาการวิ่ง	ตัวอย่างอัลกอริธึม
เวลาคงที่		${\displaystyle O(1)}$	10	การหาค่ามัธยฐานในอาร์เรย์ตัวเลขที่เรียงลำดับแล้ว การคำนวณ ( −1) n
เวลาแอคเคอร์แมนผกผัน		${\displaystyle O{\bigl (}\alpha (n){\bigr )}}$		เวลาเฉลี่ยต่อการดำเนินการโดยใช้เซตที่ไม่ซ้ำกัน
เวลาลอการิทึมแบบวนซ้ำ		${\displaystyle O(\log ^{*}n)}$		การระบายสีแบบกระจายของวงจร
ลอการิทึม-ลอการิทึม		${\displaystyle O(\log \log n)}$		เวลาเฉลี่ยต่อการดำเนินการโดยใช้คิวลำดับความสำคัญ แบบจำกัด [ 2 ]
เวลาลอการิทึม	ดล็อกไทม์	${\displaystyle O(\log n)}$	${\displaystyle \log n}$,${\displaystyle \log(n^{2})}$	การค้นหาแบบไบนารี
เวลาพหุลอการิทมิก		${\displaystyle {\textsf {poly}}(\log n)}$	${\displaystyle (\log n)^{2}}$
กำลังเศษส่วน		${\displaystyle O(n^{c})}$ที่ไหน${\displaystyle 0<c<1}$	${\displaystyle {\sqrt {n}}}$,${\displaystyle n^{\frac {2}{3}}}$	การค้นหาช่วงใน โครงสร้างต้นไม้ k -d
เวลาเชิงเส้น		${\displaystyle O(n)}$	n ,${\displaystyle 2n+5}$	การค้นหารายการที่เล็กที่สุดหรือใหญ่ที่สุดในอาร์เรย์ ที่ยัง ไม่ ได้เรียง ลำดับ อัลกอริทึมของคาดาเนะการค้นหาเชิงเส้น
เวลา "n log-star n"		${\displaystyle O(n\log ^{*}n)}$		อัลกอริทึม การสร้างสามเหลี่ยมจากรูปหลายเหลี่ยมของSeidel
เวลาเชิงเส้น		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$,${\displaystyle \log n!}$	การเรียงลำดับแบบเปรียบเทียบที่เร็วที่สุดการ แปลงฟูริเยร์ แบบ เร็ว
เวลากึ่งเชิงเส้น		${\displaystyle n{\textsf {poly}}(\log n)}$	${\displaystyle n\log ^{2}n}$	การประเมินพหุนามหลายจุด
เวลากำลังสอง		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	การเรียงลำดับแบบบับเบิลการเรียงลำดับแบบแทรก การเรียงลำดับ แบบคอนโวลูชันโดยตรง
เวลาลูกบาศก์		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	การคูณเมทริกซ์สองเมทริกซ์แบบง่ายๆ การคำนวณค่าสัมประสิทธิ์ สหสัมพันธ์บางส่วน${\displaystyle n\times n}$
เวลาพหุนาม	พี	${\displaystyle 2^{O(\log n)}={\textsf {poly}}(n)}$	${\displaystyle n^{2}+n}$,${\displaystyle n^{10}}$	อัลกอริทึมของ Karmarkarสำหรับ การ เขียนโปรแกรมเชิงเส้นการทดสอบความเป็นจำนวนเฉพาะ AKS [ 3 ] [ 4 ]
เวลากึ่งพหุนาม	คิวพี	${\displaystyle 2^{{\textsf {poly}}(\log n)}}$	${\displaystyle n^{\log \log n}}$,${\displaystyle n^{\log n}}$	อัลกอริทึมการประมาณค่าO (log 2 n )ที่รู้จักกันดีที่สุดสำหรับปัญหาต้นไม้ Steiner ที่มีทิศทาง ตัว แก้เกมพาริตีที่รู้จักกันดีที่สุด[ 5 ]อัลกอริ ทึมไอโซมอร์ฟิซึมกราฟที่รู้จักกันดีที่สุด
เวลาต่ำกว่าเลขชี้กำลัง(นิยามแรก)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$สำหรับทุกคน${\displaystyle \epsilon >0}$		ประกอบด้วยBPPเว้นแต่ EXPTIME (ดูด้านล่าง) จะเท่ากับ MA [ 6 ]
เวลาต่ำกว่าเลขชี้กำลัง(นิยามที่สอง)		${\displaystyle 2^{o(n)}}$	${\displaystyle 2^{\sqrt[{3}]{n}}}$	อัลกอริทึมคลาสสิกที่ดีที่สุดสำหรับการแยกตัวประกอบจำนวนเต็ม อัลกอริทึมที่ดีที่สุดเดิมสำหรับการหาความเหมือนกันของกราฟ
เวลาแบบเลขชี้กำลัง(ด้วยเลขชี้กำลังเชิงเส้น)	อี	${\displaystyle 2^{O(n)}}$	${\displaystyle 1.1^{n}}$,${\displaystyle 10^{n}}$	การแก้ปัญหาพนักงานขายเดินทางโดยใช้การเขียนโปรแกรมเชิงพลวัต
เวลาแฟกทอเรียล		${\displaystyle O(n)!=2^{O(n\log n)}}$	${\displaystyle n!,n^{n},2^{n\log n}}$	การแก้ปัญหาพนักงานขายเดินทางโดยใช้การค้นหาแบบบรูทฟอร์ซ
เวลาเลขชี้กำลัง	เวลาหมดอายุ	${\displaystyle 2^{{\textsf {poly}}(n)}}$	${\displaystyle 2^{n}}$,${\displaystyle 2^{n^{2}}}$	การแก้ปัญหาการคูณเมทริกซ์แบบลูกโซ่โดยใช้ การค้นหา แบบบรูทฟอร์ซการค้นหากลยุทธ์ที่ชนะในหมากรุกหมากฮอสหรือโกะโดยใช้กฎโคของญี่ปุ่นบนกระดาน ${\displaystyle n\times n}$
เวลาเลขชี้กำลังสองเท่า	2-EXPTIME	${\displaystyle 2^{2^{{\textsf {poly}}(n)}}}$	${\displaystyle 2^{2^{n}}}$	การตัดสินความจริงของข้อความที่กำหนดในเลขคณิตเพรสเบอร์เกอร์

อัลกอริทึมจะถูกเรียกว่าใช้เวลาคงที่ (มักแสดงด้วยสัญลักษณ์เวลา) เมื่อฟังก์ชันความซับซ้อนของมันถูกจำกัดด้วยค่าที่ไม่เปลี่ยนแปลงตามขนาดของข้อมูลนำเข้า ซึ่งหมายความว่าเวลาในการประมวลผลจะคงที่เสมอไม่ว่าจะประมวลผลข้อมูลมากน้อยเพียงใด ตัวอย่างเช่น การเข้าถึงองค์ประกอบเฉพาะในอาร์เรย์เป็นการดำเนินการที่ใช้เวลาคงที่ เนื่องจากต้องใช้การดำเนินการเพียงครั้งเดียวในการค้นหาองค์ประกอบนั้น ${\textstyle O(1)}$${\textstyle T(n)}$

ในทางตรงกันข้าม การหาค่าต่ำสุดในอาร์เรย์ที่ไม่มีลำดับนั้นไม่ใช่กระบวนการที่ใช้เวลาคงที่ เนื่องจากต้องตรวจสอบแต่ละองค์ประกอบทำให้มีความซับซ้อนของเวลาเชิงเส้น หรืออย่างไรก็ตาม หากทราบจำนวนองค์ประกอบและกำหนดไว้ตายตัว งานบางอย่างก็ยังสามารถพิจารณาได้ว่าใช้เวลาคงที่ ${\textstyle O(n)}$

ที่สำคัญ คำว่า "เวลาคงที่" ไม่ได้หมายความว่าเวลาในการทำงานจะต้องเป็นอิสระจากขนาดของปัญหาโดยสิ้นเชิง แต่หมายความว่าเวลาในการทำงานควรมีขอบเขตบนที่สม่ำเสมอโดยไม่ขึ้นอยู่กับขนาดของข้อมูลป้อนเข้า ตัวอย่างเช่น งานที่เกี่ยวข้องกับการสลับค่าของaและbเพื่อให้แน่ใจว่าเงื่อนไขเป็นไปตามที่กำหนด จะถูกจัดประเภทเป็นเวลาคงที่ แม้ว่าเวลาในการดำเนินการอาจแตกต่างกันไปขึ้นอยู่กับว่าเงื่อนไขนั้นเป็นไปตามที่กำหนดแล้วหรือไม่ กุญแจสำคัญคือต้องมีค่าคงที่t อยู่ค่าหนึ่ง ซึ่งเวลาที่ใช้จะไม่เกินt เสมอ ไม่ว่าค่าของข้อมูลป้อนเข้า จะเป็นเท่าใดก็ตาม${\textstyle a\leq b}$

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

กล่าวกันว่าอัลกอริทึมใช้เวลาแบบลอการิทึมเมื่อเนื่องจากและมีความสัมพันธ์กันด้วยตัวคูณคงที่และตัวคูณดังกล่าวไม่เกี่ยวข้องกับการจำแนกประเภทบิ๊กโอ ดังนั้นการใช้งานมาตรฐานสำหรับอัลกอริทึมที่ใช้เวลาแบบลอการิทึมจึงไม่ขึ้นอยู่กับฐานของลอการิทึมที่ปรากฏในนิพจน์ของ T${\displaystyle T(n)=O(\log n)}$${\displaystyle \log _{a}n}$${\displaystyle \log _{b}n}$${\displaystyle O(\log n)}$

อัลกอริทึมที่ใช้เวลาในระดับลอการิทึมมักพบได้ในการดำเนินการกับต้นไม้ไบนารีหรือเมื่อใช้การค้นหาแบบไบนารี

อัลกอริทึมจะถือว่ามีประสิทธิภาพสูง หากอัตราส่วนของจำนวนการดำเนินการต่อขนาดของข้อมูลนำเข้าลดลงและมีแนวโน้มเข้าใกล้ศูนย์เมื่อn เพิ่มขึ้น อัลกอริทึมที่ต้องเข้าถึงองค์ประกอบทั้งหมดของข้อมูลนำเข้าจะไม่สามารถใช้เวลาในระดับลอการิทึมได้ เนื่องจากเวลาที่ใช้ในการ อ่าน ข้อมูลนำเข้าขนาดnจะอยู่ในระดับเดียวกับn²${\displaystyle O(\log n)}$

ตัวอย่างของเวลาแบบลอการิทึมคือการค้นหาในพจนานุกรม พิจารณาพจนานุกรมDที่มี รายการ nรายการ เรียงตามลำดับตัวอักษรเราสมมติว่า สำหรับn > 0 เราสามารถเข้าถึง รายการที่ kของพจนานุกรมได้ในเวลาคงที่ ให้แทน รายการที่ k นี้ ภายใต้สมมติฐานเหล่านี้ การทดสอบว่าคำwอยู่ในพจนานุกรมหรือไม่ สามารถทำได้ในเวลาแบบลอการิทึม: พิจารณาโดยที่แทนฟังก์ชันปัดเศษ ลง ถ้า—นั่นคือ คำwอยู่ตรงกลางของพจนานุกรมพอดี—เราก็เสร็จสิ้น มิฉะนั้น ถ้า—นั่นคือ ถ้าคำwมาก่อนคำตรงกลางในลำดับตัวอักษรของพจนานุกรมทั้งหมด—เราจะค้นหาต่อไปในลักษณะเดียวกันในครึ่งซ้าย (นั่นคือ ครึ่งก่อนหน้า) ของพจนานุกรม และทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจะพบคำที่ถูกต้อง มิฉะนั้น ถ้าคำ w อยู่หลังคำตรงกลาง ให้ดำเนินการในทำนองเดียวกันกับครึ่งขวาของพจนานุกรม อัลกอริทึมนี้คล้ายกับวิธีการที่มักใช้ในการค้นหารายการในพจนานุกรมกระดาษ ดังนั้น พื้นที่การค้นหาภายในพจนานุกรมจึงลดลงเมื่ออัลกอริทึมเข้าใกล้คำเป้าหมายมากขึ้น ${\displaystyle 1\leq k\leq n}$${\displaystyle D(k)}$${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle \lfloor \;\rfloor }$${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$

กล่าวกันว่าอัลกอริทึมทำงานในเวลาพหุโลการิทึมถ้าเวลาของอัลกอริทึมนั้นคือสำหรับค่าคงที่k บางค่า อีกวิธีหนึ่งในการเขียนคือ ${\displaystyle T(n)}$${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$${\displaystyle O(\log ^{k}n)}$

ตัวอย่างเช่นการเรียงลำดับโซ่เมทริกซ์สามารถแก้ไขได้ในเวลาพหุลอการิทึมบนเครื่องเข้าถึงแบบสุ่มขนาน [ ^{7 ]}และกราฟสามารถกำหนดให้เป็นระนาบได้^ในลักษณะไดนามิกอย่างสมบูรณ์ในเวลาต่อการดำเนินการแทรก/ลบ^{[ 8 ]}${\displaystyle O(\log ^{3}n)}$

กล่าวได้ว่าอัลกอริทึมทำงานในเวลาต่ำกว่าเชิงเส้น ( sub- linear time ) ถ้าโดยเฉพาะอย่างยิ่ง อัลกอริทึมที่มีความซับซ้อนเชิงเวลาตามที่กำหนดไว้ข้างต้นนั้นจะต้อง ทำงานในเวลาต่ำกว่าเชิงเส้น${\displaystyle T(n)=o(n)}$

คำว่าอัลกอริทึมเวลาแบบซับลิเนียร์โดยเฉพาะมักหมายถึงอัลกอริทึมแบบสุ่มที่สุ่มตัวอย่างเศษส่วนเล็ก ๆ ของอินพุตและประมวลผลอย่างมีประสิทธิภาพเพื่ออนุมานคุณสมบัติของอินสแตนซ์ทั้งหมดโดยประมาณ^{[ 9 ]} อัลกอริทึมเวลาแบบซับลิเนีย ร์ ประเภทนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับการทดสอบคุณสมบัติและสถิติ

สถานการณ์อื่นๆ ที่อัลกอริธึมสามารถทำงานได้ในเวลาต่ำกว่าเชิงเส้น ได้แก่:

• อัลกอริทึมแบบขนานที่มีปริมาณงาน รวมเชิงเส้นหรือมากกว่า (ทำให้สามารถอ่านข้อมูลอินพุตทั้งหมดได้) แต่มีความลึก ต่ำกว่า เชิง เส้น
• อัลกอริทึมที่มีข้อสมมติฐานที่รับประกันได้เกี่ยวกับโครงสร้างของข้อมูลป้อนเข้า ตัวอย่างที่สำคัญคือการดำเนินการกับโครงสร้างข้อมูลเช่นการค้นหาแบบไบนารีในอาร์เรย์ที่เรียงลำดับแล้ว
• อัลกอริทึมที่ค้นหาโครงสร้างเฉพาะที่ในอินพุต เช่น การค้นหาค่าต่ำสุดเฉพาะที่ในอาร์เรย์ 1 มิติ (สามารถแก้ไขได้ใน  เวลาโดยใช้การค้นหาแบบไบนารีรูปแบบหนึ่ง) แนวคิดที่เกี่ยวข้องอย่างใกล้ชิดคืออัลกอริทึมการคำนวณเฉพาะที่ (LCA)ซึ่งอัลกอริทึมจะรับอินพุตขนาดใหญ่และสอบถามข้อมูลเฉพาะที่เกี่ยวกับเอาต์พุตขนาดใหญ่ที่ถูกต้อง^{[ 10 ]}${\displaystyle O(\log(n))}$

กล่าวกันว่าอัลกอริทึมใช้เวลาเชิงเส้นหรือเวลาเชิงเส้น ถ้าความซับซ้อนเชิงเวลาของมันคือσ² โดยทั่วไปแล้ว หมายความว่าเวลาในการทำงานจะเพิ่มขึ้นอย่างมากที่สุดเป็นเชิงเส้นตามขนาดของข้อมูลนำเข้า กล่าวให้แม่นยำยิ่งขึ้น หมายความว่ามีค่าคงที่cที่ทำให้เวลาในการทำงานมีค่าไม่เกิน σ² สำหรับทุกข้อมูลนำเข้าที่มีขนาดnตัวอย่างเช่น ขั้นตอนการบวกองค์ประกอบทั้งหมดของลิสต์ต้องใช้เวลาแปรผันตรงกับความยาวของลิสต์ ถ้าเวลาในการบวกมีค่าคงที่ หรืออย่างน้อยก็ถูกจำกัดด้วยค่าคงที่ ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle cn}$

เวลาเชิงเส้น (Linear time) คือความซับซ้อนของเวลาที่ดีที่สุดเท่าที่จะเป็นไปได้ในสถานการณ์ที่อัลกอริทึมต้องอ่านข้อมูลเข้าทั้งหมดตามลำดับ ดังนั้นจึงมีการวิจัยมากมายที่มุ่งเน้นไปที่การค้นหาอัลกอริทึมที่มีเวลาเชิงเส้น หรืออย่างน้อยก็ใกล้เคียงกับเวลาเชิงเส้น การวิจัยนี้รวมถึงวิธีการทั้งด้านซอฟต์แวร์และฮาร์ดแวร์ มีเทคโนโลยีฮาร์ดแวร์หลายอย่างที่ใช้ประโยชน์จากความขนานเพื่อให้ได้ผลลัพธ์นี้ ตัวอย่างเช่นหน่วยความจำที่สามารถระบุตำแหน่งตามเนื้อหา (Content-addressable memory ) แนวคิดเรื่องเวลาเชิงเส้นนี้ถูกนำมาใช้ในอัลกอริทึมการจับคู่สตริง เช่น อัลกอริทึมการค้นหาสตริง ของ Boyer–Mooreและอัลกอริทึมของ Ukkonen

กล่าวกันว่าอัลกอริทึมทำงานในเวลากึ่งเชิงเส้น (เรียกอีกอย่างว่าเวลาลอการิทึมเชิงเส้น ) ถ้า สำหรับค่าคงที่บวก kบางค่า[ ^{11 ]}เวลาเชิงเส้นคือกรณี^{[ 12 ]}โดยใช้สัญกรณ์ O แบบอ่อน อัลกอริ^ทึมเหล่านี้คืออัลกอริทึมเวลากึ่งเชิงเส้นยังเป็นสำหรับค่าคงที่ทุกค่า และดังนั้นจึงทำงานได้เร็วกว่าอัลกอริทึมเวลาพหุนามใด ๆที่ขอบเขตเวลารวมถึงพจน์สำหรับค่าคงที่ใดๆ ${\displaystyle T(n)=O(n\log ^{k}n)}$${\displaystyle k=1}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{c}}$${\displaystyle c>1}$

อัลกอริทึมที่ทำงานในเวลาแบบกึ่งเชิงเส้น ได้แก่:

• การเรียงลำดับแบบผสานในตำแหน่งเดิม ( In-place merge sort)${\displaystyle O(n\log ^{2}n)}$
• อัลกอริ ทึมQuickSortในเวอร์ชันแบบสุ่ม มีเวลาการทำงานโดยเฉลี่ยเมื่อพิจารณาจากกรณีที่เลวร้ายที่สุด ส่วนเวอร์ชันที่ไม่ใช้การสุ่ม มีเวลาการทำงานเมื่อพิจารณาจากความซับซ้อนโดยเฉลี่ยเท่านั้น${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$
• ฮีปซอร์ต , เมอร์จซอร์ต, อินโทรซอร์ต , ไบนารีทรีซอร์ต, สมูทซอร์ต , แพตตี้ซอร์ตติ้งฯลฯ ในกรณีที่เลวร้ายที่สุด${\displaystyle O(n\log n)}$
• การแปลงฟูริเยร์แบบเร็ว${\displaystyle O(n\log n)}$
• การคำนวณอาร์เรย์ Monge${\displaystyle O(n\log n)}$
• อัลกอริทึมSchönhage–Strassenสำหรับการคูณ${\displaystyle O(n\log n\log \log n)}$

ในหลายกรณีเวลาในการทำงานเป็นเพียงผลลัพธ์ของการดำเนินการซ้ำnครั้ง (สำหรับสัญลักษณ์ โปรดดูสัญลักษณ์ Big O § ตระกูลสัญลักษณ์ Bachmann–Landau ) ตัวอย่างเช่นการเรียงลำดับแบบต้นไม้ไบนารีสร้างต้นไม้ไบนารีโดยการแทรกแต่ละองค์ประกอบของ อาร์เรย์ขนาด nทีละรายการ เนื่องจากการดำเนินการแทรกในต้นไม้ค้นหาไบนารีแบบปรับสมดุลตัวเองใช้เวลา ดังนั้นอัลกอริทึมทั้งหมดจึงใช้เวลา ${\displaystyle O(n\log n)}$${\displaystyle \Theta (\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

การเรียงลำดับแบบเปรียบเทียบต้องใช้การเปรียบเทียบอย่างน้อยในกรณีที่เลวร้ายที่สุด เนื่องจากตามการประมาณของสเตอร์ลิงนอกจากนี้ยังมักเกิดขึ้นจากความสัมพันธ์เวียนเกิดด้วย ${\displaystyle \Omega (n\log n)}$${\displaystyle \log(n!)=\Theta (n\log n)}$${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

กล่าวได้ว่าอัลกอริทึมมีเวลาการทำงานต่ำกว่ากำลังสองถ้า. ${\displaystyle T(n)=o(n^{2})}$

ตัวอย่างเช่น อัลก อริทึมการเรียงลำดับ แบบง่ายๆ ที่ใช้การเปรียบเทียบ นั้นใช้เวลาประมวลผลระดับกำลังสอง (เช่น การเรียงลำดับแบบแทรก ) แต่ก็มีอัลกอริทึมขั้นสูงกว่าที่ใช้เวลาประมวลผลต่ำกว่ากำลังสอง (เช่นการเรียงลำดับแบบเชลล์ ) ไม่มีอัลกอริทึมการเรียงลำดับทั่วไปใดที่ใช้เวลาประมวลผลเชิงเส้น แต่การเปลี่ยนแปลงจากระดับกำลังสองไปเป็นระดับต่ำกว่ากำลังสองนั้นมีความสำคัญอย่างยิ่งในทางปฏิบัติ

กล่าวกันว่าอัลกอริทึมมีเวลาพหุนามหากเวลาการทำงานของอัลกอริทึมนั้นมี^{ขอบเขต}บนโดย นิพจน์ พหุนามในขนาดของอินพุตสำหรับอัลกอริทึม นั่นคือT ( n ) = O ( nk ) สำหรับค่าคงที่ บวกkบางค่า^{[ 1 ] [ 13 ]}ปัญหาที่มีอัลกอริทึมเวลาพหุนามแบบกำหนดได้นั้นจัดอยู่ในชั้นความซับซ้อนPซึ่งเป็นศูนย์กลางในสาขาทฤษฎีความซับซ้อนของการคำนวณวิทยานิพนธ์ของ Cobhamระบุว่าเวลาพหุนามเป็นคำพ้องความหมายของ "จัดการได้" "เป็นไปได้" "มีประสิทธิภาพ" หรือ "เร็ว" ^{[ 14 ]}

ตัวอย่างของอัลกอริธึมที่ทำงานในเวลาพหุนาม:

• อั ลกอริทึมการเรียงลำดับ แบบ Selection Sortบน จำนวนเต็ม nตัว จะทำการคำนวณโดยใช้ค่าคงที่A บางค่า ดังนั้นจึงใช้เวลาและเป็นอัลกอริทึมแบบเวลาพหุนาม${\displaystyle An^{2}}$${\displaystyle O(n^{2})}$
• การคำนวณทางคณิตศาสตร์พื้นฐานทั้งหมด (การบวก การลบ การคูณ การหาร และการเปรียบเทียบ) สามารถทำได้ในเวลาพหุนาม
• การจับคู่สูงสุดในกราฟสามารถทำได้ในเวลาพหุนาม ในบางบริบท โดยเฉพาะอย่างยิ่งในการเพิ่มประสิทธิภาพจะมีการแยกแยะระหว่าง อัลกอริทึม ที่ใช้เวลาพหุนามอย่างเข้มงวดและอัลกอริทึมที่ใช้เวลาพหุนามอย่างอ่อน

แนวคิดทั้งสองนี้จะมีความเกี่ยวข้องก็ต่อเมื่อข้อมูลที่ป้อนเข้าสู่อัลกอริทึมประกอบด้วยจำนวนเต็มเท่านั้น

แนวคิดเรื่องเวลาพหุนามนำไปสู่ระดับความซับซ้อนหลายระดับในทฤษฎีความซับซ้อนของการคำนวณ ระดับความซับซ้อนที่สำคัญบางระดับที่กำหนดโดยใช้เวลาพหุนามมีดังต่อไปนี้

• P :ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้บนเครื่องทัวริงแบบกำหนดได้ในเวลาพหุนาม
• NP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้บนเครื่องทัวริงแบบไม่กำหนด (non-deterministic Turing machine)ในเวลาพหุนาม (polynomial time)
• ZPP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยไม่มีข้อผิดพลาดบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• RP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยมีข้อผิดพลาดด้านเดียวบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• BPP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้โดยมีข้อผิดพลาดสองด้านบนเครื่องทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม
• BQP : ระดับความซับซ้อนของปัญหาการตัดสินใจที่สามารถแก้ไขได้ด้วยข้อผิดพลาดสองด้านบนเครื่องทัวริงควอนตัมในเวลาพหุนาม

P คือระดับความซับซ้อนของเวลาที่น้อยที่สุดบนเครื่องจักรเชิงกำหนด ซึ่งมีความทนทานต่อการเปลี่ยนแปลงแบบจำลองของเครื่องจักร (ตัวอย่างเช่น การเปลี่ยนจากเครื่องจักรทัวริงแบบเทปเดี่ยวไปเป็นเครื่องจักรแบบหลายเทปอาจทำให้ความเร็วเพิ่มขึ้นเป็นกำลังสอง แต่ขั้นตอนวิธีใดๆ ที่ทำงานในเวลาพหุนามภายใต้แบบจำลองหนึ่ง ก็จะทำงานในเวลาพหุนามภายใต้แบบจำลองอื่นเช่นกัน) เครื่องจักรนามธรรม ใดๆ จะมีระดับความซับซ้อนที่สอดคล้องกับปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องจักรนั้น

อัลกอริทึมจะถูกกำหนดให้ใช้เวลา ซูเปอร์พหุนามหากT ( n ) ไม่ถูกจำกัดค่าบนด้วยพหุนามใดๆ กล่าวคือ ถ้าสำหรับจำนวนเต็ม บวก ${\displaystyle T(n)\not \in O(n^{c})}$cทุกตัว

ตัวอย่างเช่น อัลกอริทึมที่ใช้เวลา2nขั้นตอนในการประมวลผลข้อมูลขนาดn จะต้อง ^ใช้เวลามากกว่าพหุนาม (หรือเวลาแบบเลขชี้กำลัง)

อัลกอริทึมที่ใช้ทรัพยากรแบบเลขชี้กำลังนั้นเห็นได้ชัดว่าเป็นซูเปอร์พหุนาม แต่บางอัลกอริทึมก็เป็นซูเปอร์พหุนามที่อ่อนมากเท่านั้น ตัวอย่างเช่นการทดสอบความเป็นจำนวนเฉพาะของ Adleman–Pomerance–Rumelyใช้ เวลา n ^{O (log log n )}ในการ ประมวลผลข้อมูลอินพุต n บิต ซึ่งเติบโตเร็วกว่าพหุนามใดๆ สำหรับ nที่มากพอแต่ขนาดของข้อมูลอินพุตจะต้องมีขนาดใหญ่จนไม่สามารถใช้งานได้จริงก่อนที่จะไม่สามารถถูกครอบงำโดยพหุนามที่มีดีกรีน้อยได้

อัลกอริทึมที่ต้องใช้เวลาประมวลผลระดับซูเปอร์พหุนามนั้นอยู่นอกเหนือระดับความซับซ้อนPวิทยานิพนธ์ของ Cobhamระบุว่าอัลกอริทึมเหล่านี้ไม่สามารถนำไปใช้ได้จริง และในหลายกรณีก็เป็นเช่นนั้น เนื่องจากปัญหา P เทียบกับ NPยังไม่ได้รับการแก้ไข จึงไม่ทราบว่า ปัญหา NP-completeต้องใช้เวลาประมวลผลระดับซูเปอร์พหุนามหรือไม่

อัลกอริ ทึมเวลาควาซีพหุนาม (Quasi-polynomial time algorithms) คืออัลกอริทึมที่มีเวลาการทำงานแสดงการเติบโตแบบควาซีพหุนามซึ่งเป็นพฤติกรรมที่อาจช้ากว่าเวลาพหุนาม แต่เร็วกว่าเวลาเลขชี้กำลัง อย่างมาก เวลาการทำงานในกรณีที่เลวร้ายที่สุดของอัลกอริทึมเวลาควาซีพหุนามคือสำหรับค่าคงที่บางค่าเมื่อค่านี้จะให้เวลาพหุนาม และเมื่อค่านี้จะให้เวลาต่ำกว่าเชิงเส้น (sub-linear time) ${\displaystyle 2^{O(\log ^{c}n)}}$${\displaystyle c>0}$${\displaystyle c=1}$${\displaystyle c<1}$

มีปัญหาบางอย่างที่เราทราบว่ามีอัลกอริทึมที่ใช้เวลาทำงานแบบกึ่งพหุนาม แต่ยังไม่มีอัลกอริทึมที่ใช้เวลาทำงานแบบพหุนาม ปัญหาเหล่านี้เกิดขึ้นในอัลกอริทึมการประมาณค่า ตัวอย่างที่มีชื่อเสียงคือปัญหาต้นไม้สไตเนอร์ แบบมีทิศทาง ซึ่งมีอัลกอริทึมการประมาณค่าที่ใช้เวลาทำงานแบบกึ่งพหุนาม โดยได้ค่าประมาณเท่ากับ( โดยที่ nคือจำนวนจุดยอด) แต่การพิสูจน์ว่ามีอัลกอริทึมที่ใช้เวลาทำงานแบบพหุนามดังกล่าวอยู่จริงนั้นยังคงเป็นปัญหาที่ยังไม่มีคำตอบ ${\displaystyle O(\log ^{3}n)}$

ปัญหาการคำนวณอื่นๆ ที่มีวิธีแก้ปัญหาแบบกึ่งพหุนามแต่ไม่มีวิธีแก้ปัญหาแบบพหุนามที่ทราบ ได้แก่ ปัญหา คลิกที่ถูกปลูกฝังซึ่งเป้าหมายคือการค้นหาคลิกขนาดใหญ่ในการรวมกันของคลิกและกราฟสุ่มแม้ว่าจะสามารถแก้ได้แบบกึ่งพหุนาม แต่ก็มีการคาดเดาว่าปัญหาคลิกที่ถูกปลูกฝังไม่มีวิธีแก้ปัญหาแบบพหุนาม การคาดเดาเรื่องคลิกที่ถูกปลูกฝังนี้ถูกนำมาใช้เป็นสมมติฐานความยากในการคำนวณเพื่อพิสูจน์ความยากของปัญหาอื่นๆ อีกหลายปัญหาในทฤษฎีเกม เชิง คำนวณการทดสอบคุณสมบัติและ การเรียน รู้ของเครื่อง^{[ 15 ]}

คลาสความซับซ้อนQPประกอบด้วยปัญหาทั้งหมดที่มีอัลกอริทึมเวลากึ่งพหุนาม สามารถกำหนดได้ในแง่ของDTIMEดังต่อไปนี้^{[ 16 ]}

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}$

ในทฤษฎีความซับซ้อน ปัญหา P เทียบกับ NP ที่ยังแก้ไม่ตก นั้นถามว่า ปัญหาทั้งหมดใน NP มีอัลกอริทึมที่ใช้เวลาแบบพหุนามหรือไม่ อัลกอริทึมที่เป็นที่รู้จักดีที่สุดสำหรับ ปัญหา NP-completeเช่น 3SAT เป็นต้น ใช้เวลาแบบเลขชี้กำลัง อันที่จริง มีการตั้งข้อสันนิษฐานสำหรับปัญหา NP-complete ตามธรรมชาติหลายปัญหาว่าไม่มีอัลกอริทึมที่ใช้เวลาต่ำกว่าเลขชี้กำลัง ในที่นี้ "เวลาต่ำกว่าเลขชี้กำลัง" หมายถึงความหมายที่สองที่นำเสนอไว้ด้านล่าง (ในทางกลับกัน ปัญหาเกี่ยวกับกราฟหลายปัญหาที่แสดงในรูปแบบธรรมชาติโดยเมทริกซ์ประชิดสามารถแก้ไขได้ในเวลาต่ำกว่าเลขชี้กำลังเพียงเพราะขนาดของข้อมูลนำเข้าเป็นกำลังสองของจำนวนจุดยอด) ข้อสันนิษฐานนี้ (สำหรับปัญหา k-SAT) เรียกว่าสมมติฐานเวลาแบบเลขชี้กำลัง^{[ 17 ]}เนื่องจากมีการคาดเดาว่าปัญหา NP-complete ไม่มีอัลกอริทึมเวลาแบบกึ่งพหุนาม ผลลัพธ์ที่ไม่สามารถประมาณค่าได้บางส่วนในสาขาอัลกอริทึมการประมาณค่าจึงตั้งสมมติฐานว่าปัญหา NP-complete ไม่มีอัลกอริทึมเวลาแบบกึ่งพหุนาม ตัวอย่างเช่น ดูผลลัพธ์ที่ไม่สามารถประมาณค่าได้ที่ทราบสำหรับปัญหา การครอบคลุมเซต

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

กล่าวได้ว่าปัญหาสามารถแก้ไขได้ในเวลาต่ำกว่าเลขชี้กำลัง หากสามารถแก้ไขได้ในเวลาการทำงานซึ่งลอการิทึมเติบโตน้อยกว่าพหุนามใดๆ ที่กำหนดไว้ กล่าวให้แม่นยำยิ่งขึ้น ปัญหาจะอยู่ในเวลาต่ำกว่าเลขชี้กำลัง หากสำหรับทุกε > 0จะมีอัลกอริทึมที่แก้ปัญหาได้ในเวลาO (2 ^{n ε} ) เซตของปัญหาทั้งหมดดังกล่าวคือคลาสความซับซ้อนSUBEXPซึ่งสามารถกำหนดได้ในแง่ของDTIMEดังต่อไปนี้^{[ 6 ] [ 19 ] [ 20 ] [ 21 ]}

${\displaystyle {\textsf {SUBEXP}}=\bigcap _{\varepsilon >0}{\textsf {DTIME}}\left(2^{n^{\varepsilon }}\right)}$

แนวคิดเรื่องค่าต่ำกว่าเลขชี้กำลังนี้ไม่สม่ำเสมอในแง่ของεในแง่ที่ว่าεไม่ใช่ส่วนหนึ่งของข้อมูลนำเข้า และ ε แต่ละค่าอาจมีอัลกอริทึมเฉพาะของตนเองสำหรับปัญหาดังกล่าว

ผู้เขียนบางคนกำหนดเวลาต่ำกว่าเลขชี้กำลังเป็นเวลาการทำงานใน. ^{[ 17 ] [ 22 ] [ 23 ]}คำจำกัดความนี้อนุญาตให้มีเวลาการทำงานที่มากกว่าคำจำกัดความแรกของเวลาต่ำกว่าเลขชี้กำลัง ตัวอย่างของอัลกอริทึมที่มีเวลาต่ำกว่าเลขชี้กำลังดังกล่าวคืออัลกอริทึมคลาสสิกที่รู้จักกันดีที่สุดสำหรับการแยกตัวประกอบจำนวนเต็ม นั่นคือตะแกรงฟิลด์จำนวนทั่วไปซึ่งทำงานในเวลาประมาณโดยที่ความยาวของอินพุตคือnอีกตัวอย่างหนึ่งคือปัญหาความเหมือนกันของกราฟซึ่งอัลกอริทึมที่รู้จักกันดีที่สุดตั้งแต่ปี 1982 ถึง 2016 แก้ได้ในอย่างไรก็ตามในงาน STOC 2016 ได้มีการนำเสนออัลกอริทึมที่มีเวลาแบบกึ่งพหุนาม^{[ 24 ]}${\displaystyle 2^{o(n)}}$${\displaystyle 2^{{O}(n^{1/3}(\log n)^{2/3})}}$${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$

ความแตกต่างอยู่ที่ว่าอัลกอริทึมได้รับอนุญาตให้เป็นแบบย่อยเลขชี้กำลังในขนาดของอินสแตนซ์ จำนวนจุดยอด หรือจำนวนขอบ ในความซับซ้อนแบบพารามิเตอร์ความแตกต่างนี้จะถูกทำให้ชัดเจนโดยการพิจารณาคู่ของปัญหาการตัดสินใจและพารามิเตอร์ k SUBEPTคือคลาสของปัญหาพารามิเตอร์ทั้งหมดที่ทำงานในเวลาแบบย่อยเลขชี้กำลังในkและแบบพหุนามในขนาดอินพุตn : ^{[ 25 ]}${\displaystyle (L,k)}$

${\displaystyle {\textsf {SUBEPT}}={\textsf {DTIME}}\left(2^{o(k)}\cdot {\textsf {poly}}(n)\right).}$

กล่าวโดยละเอียดแล้ว SUBEPT คือกลุ่มของปัญหาพารามิเตอร์ทั้งหมดที่มีฟังก์ชันที่คำนวณได้และอัลกอริทึมที่ตัดสินค่าL ได้ ในเวลา ${\displaystyle (L,k)}$${\displaystyle f:\mathbb {N} \to \mathbb {N} }$${\displaystyle f\in o(k)}$${\displaystyle 2^{f(k)}\cdot {\textsf {poly}}(n)}$

สมมติฐานเวลาเลขชี้กำลัง ( ETH ) คือ3SAT ซึ่ง เป็นปัญหาความพึงพอใจของสูตรบูลีนในรูปแบบปกติเชิงเชื่อมโยงที่มีตัวอักษรไม่เกินสามตัวต่อข้อความและมี ตัวแปร nตัว ไม่สามารถแก้ไขได้ในเวลา 2 ^{o ( n )}กล่าวโดยละเอียด สมมติฐานคือมีค่าคงที่สัมบูรณ์c > 0 บางค่า ที่ทำให้ 3SAT ไม่สามารถตัดสินได้ในเวลา 2 ^cnโดยเครื่องจักรทัวริงเชิงกำหนดใดๆ โดยที่mแทนจำนวนข้อความ ETH เทียบเท่ากับสมมติฐานที่ว่าk SAT ไม่สามารถแก้ไขได้ในเวลา 2 ^{o ( m )}สำหรับจำนวนเต็มk ≥ 3ใด ๆ ^{[ 26 ]}สมมติฐานเวลาเลขชี้กำลังบ่งชี้ว่าP ≠ NP

กล่าวได้ว่าอัลกอริทึมมีเวลาแบบเอก^{ซ์โปเนนเชียลถ้า} T ( n )มีค่าสูงสุดไม่เกิน 2ⁿⁿ โดยที่ poly( n ) คือพหุนามบางตัวในnกล่าวอย่างเป็นทางการมากขึ้น อัลกอริทึมมีเวลาแบบเอกซ์โปเนนเชียล ถ้าT(n) มีค่าสูงสุดไม่เกิน O(2ⁿᵏ) สำหรับค่าคงที่ k บางค่าปัญหาที่ยอมรับอั^ลกอริ^ทึม เวลาแบบเอกซ์โปเนนเชียลบ น เครื่องทัวริงแบบกำหนดได้ จะจัดอยู่ในกลุ่มความซับซ้อนที่เรียกว่าEXP

${\displaystyle {\textsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\textsf {DTIME}}\left(2^{n^{c}}\right)}$

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

${\displaystyle {\textsf {E}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{cn}\right)}$

กล่าวได้ว่าอัลกอริทึมมีเวลาแฟกทอเรียลถ้าT(n)มีค่าสูงสุดไม่เกินฟังก์ชันแฟกทอเรียลn!เวลาแฟกทอเรียลเป็นเซตย่อยของเวลาเอกซ์โพเนนเชียล (EXP) เพราะสำหรับทุกn ∈ n! อย่างไรก็ตาม มันไม่ใช่เซตย่อยของ E ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$${\displaystyle \epsilon >0}$

ตัวอย่างหนึ่งของอัลกอริทึมที่ทำงานในเวลาแฟกทอเรียลคือโบโกซอร์ต (Bogosort)ซึ่งเป็นอัลกอริทึมการเรียงลำดับที่ไม่มีประสิทธิภาพอย่างมากโดยอาศัยการลองผิดลองถูก โบโกซอร์ตเรียงลำดับรายการที่มีnรายการโดยการสับเปลี่ยนรายการซ้ำ ๆ จนกว่าจะพบว่าเรียงลำดับแล้ว ในกรณีเฉลี่ย แต่ละรอบของการทำงานของอัลกอริทึมโบโกซอร์ตจะตรวจสอบลำดับหนึ่งในn ! ลำดับของ รายการ nรายการ หากรายการแตกต่างกัน จะมีเพียงลำดับเดียวเท่านั้นที่ถูกเรียงลำดับ โบโกซอร์ตมีที่มาเดียวกันกับทฤษฎีลิงอนันต์ (Infinite Monkey Theorem )

กล่าวกันว่าอัลกอริทึมมี เวลา การทำงานแบบเลขชี้กำลังสองเท่า (double exponential time) ถ้าT ( n ) มีค่าสูงสุดไม่เกิน^{2²poly ( n )}โดยที่ poly( n ) เป็นพหุนามบางตัวในnอัลกอริทึมดังกล่าวจัดอยู่ในกลุ่มความซับซ้อน2- EXPTIME

${\displaystyle {\textsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\textsf {DTIME}}\left(2^{2^{n^{c}}}\right)}$

อัลกอริทึมที่มีเวลาการทำงานแบบเลขชี้กำลังสองเท่าที่เป็นที่รู้จักกันดี ได้แก่:

• ขั้นตอนการตัดสินใจสำหรับเลขคณิตของเพรสเบอร์เกอร์
• การคำนวณฐาน Gröbner (ในกรณีที่เลวร้ายที่สุด^{[ 27 ]} )
• การกำจัดตัวบ่งปริมาณในฟิลด์ปิดจริงใช้เวลาอย่างน้อยสองเท่าของเวลาเลขชี้กำลัง^{[ 28 ]}และสามารถทำได้ในเวลานี้^{[ 29 ]}

• สัญกรณ์แอล
• ความซับซ้อนของพื้นที่