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
Lecture notes for an introductory computer science course
Author: Kristina Lundqvist

-Paid-

See also

-No Additional Notes-