asymptotic complexity
(1.4 hours to learn)
Summary
The asymptotic (time) complexity of an algorithm refers to the scaling of the running time of an algorithm as a function of the input size. The time complexity is typically given in terms of big-O notation, where the running time is bounded up to a multiplicative constant.
Context
-this concept has no prerequisites-
Goals
- Know the precise definition of big-O notation
- Be able to analyze the asymptotic complexity of simple algorithms
Core resources (read/watch one of the following)
-Free-
→ MIT 16.070: Introduction to Computers and Programming
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 7.1, "Measuring complexity," pages 247-256
See also
-No Additional Notes-