# 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-