Time complexity is a measure of the amount of computer time it takes to run an algorithm. It is estimated by counting the number of elementary operations performed and expressed as a function of the size of the input. Big O notation is used to express the asymptotic behavior of the complexity. Algorithmic complexities are classified according to the type of function appearing in the big O notation.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more conceptsCarnegie Mellon University
Fall 2022
A course offering rigorous study of computation, examining the central results and questions about the nature of computation, including finite automata, computational complexity, and cryptography.
No concepts data
+ 10 more conceptsCarnegie Mellon University
Spring 2023
This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.
No concepts data
+ 29 more conceptsCarnegie Mellon University
Fall 2018
The course provides a rigorous introduction to the foundations of computer science, improving abstract thinking skills and preparing students to be innovators in the field. Topics include computation, computational complexity, and real-world applications of computational concepts. Prerequisites imply this is an intermediate-level course.
No concepts data
+ 25 more concepts