Asymptotic Analysis

Intro

We want to classify algorithms according to their time or space requirement as the input size grows. Big O $\mathcal{O}$ is represents the order of a function and works as an upper bound. It helps to put algorithms into different classes such as constant, logarithmic, linear, polynomial, and exponential.

Formal Definition

See Wikipedia

Reference

MIT 16.070

PreviousComputational Complexity NextNP-completeness

Last updated 5 years ago

Intro

We want to classify algorithms according to their time or space requirement as the input size grows. Big O

\mathcal{O}

is represents the order of a function and works as an upper bound. It helps to put algorithms into different classes such as constant, logarithmic, linear, polynomial, and exponential.