ภายหลังจากที่สามารถระบุได้ว่า ปัญหาใดสามารถแก้ได้ และปัญหาใดที่แก้ไม่ได้ เรามักจะเกิดคำถามขึ้นอีกว่าในบรรดาปัญหาที่แก้ได้ ซึ่งเป็นกลุ่มของฟังก์ชันที่คำนวณได้นั้น มีความซับซ้อนอยู่ในระดับใด จุดนี้เป็นความสนใจหลักของ ทฤษฎีความซับซ้อนในการคำนวณ

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

คำถามใดๆ คำถามหนึ่งจะถูกเรียกว่า "ตัวอย่างปัญหา" (instance) ในกรณีนี้ เราจะเรียก "จงหาตัวประกอบที่เป็นจำนวนเฉพาะของ 15" ว่าเป็นตัวอย่างปัญหาของปัญหาแยกตัวประกอบ

เราจะนิยาม ความซับซ้อนด้านเวลา (time complexity) สำหรับปัญหาหนึ่ง ๆ ว่าเป็นจำนวนขั้นตอนที่ใช้ในการแก้ตัวอย่างปัญหาสำหรับปัญหานั้น ในรูปฟังก์ชันของขนาดของข้อมูลป้อนเข้า (ซึ่งโดยปกติแล้วเราจะคิดขนาดเป็นบิต) โดยใช้ขั้นตอนวิธีที่มีประสิทธิภาพที่สุด ยกตัวอย่างเช่น ในปัญหา ๆ หนึ่ง สำหรับทุกตัวอย่างปัญหาที่มีขนาด n {\displaystyle n} บิต ถ้าเราสามารถแก้ตัวอย่างปัญหานี้ได้ภายใน n 2 {\displaystyle n^{2}} ขั้นตอน เราสามารถพูดได้ว่าปัญหานี้มีความซับซ้อนด้านเวลาเป็น n 2 {\displaystyle n^{2}} ซึ่งในการกล่าวถึงเวลาที่ใช้นั้น แน่นอนว่าเครื่องจักร หรือ คอมพิวเตอร์แต่ละเครื่องก็ใช้เวลาในการคำนวณแตกต่างกันไป เพื่อที่จะหลีกเลี่ยงความแตกต่างในจุดนี้ เราจะใช้สัญกรณ์โอใหญ่ (Big O notation) ปัญหาที่มีความซับซ้อนด้านเวลาเป็น O ( n 2 ) {\displaystyle O(n^{2})} ในเครื่องคอมพิวเตอร์เครื่องหนึ่ง จะมีความซับซ้อนด้านเวลาเป็น O ( n 2 ) {\displaystyle O(n^{2})} บนเครื่องอื่นๆด้วยเช่นกัน จะเห็นได้ว่าสัญกรณ์โอใหญ่ช่วยเราหลีกเลี่ยงการกล่าวถึงรายละเอียด ที่เป็นความแตกต่างระหว่างเครื่องคอมพิวเตอร์

หลายครั้งเราจะกล่าวถึงความซับซ้อนด้านเวลาว่าเป็น "เวลาที่ใช้ในการแก้ปัญหา" หรือ "เวลาที่ใช้ในการทำงาน"

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