Asymptotic Analysis

Analyzing what happens as the number of inputs becomes very large is referred to as asymptotic analysis. How does the complexity of the algorithm change when applied to ten, or one thousand, or ten million items?

Rate of Growth

Rate of growth describes how an algorithm’s complexity changes as the input size grows. This is commonly represented using Big-O notation.

Constant – O(1)

An O(1) algorithm is one whose complexity is constant regardless of how large the input size is.

Linear – O(n)

An O(n) algorithm is one whose complexity grows linearly with the size of the input

Logarithmic – O(log n)

An O(log n) algorithm is one whose complexity is logarithmic to its size. Many divide and conquer algorithms fall into this bucket.

Linearithmic – O(n log n)

A linearithmic algorithm, or log linear, is an algorithm that has a complexity of O(n log n). Some divide and conquer algorithms fall into this bucket.

Quadratic – O(n2)

An O(n2) algorithm is one whose complexity is quadratic to its size.