Asymptotic Analysis and Notation

Here, We will learn about asymptotic analysis and notation, types of notation: big-o notation, omega notation, theta notation and growth rate of algorithm.

Asymptotic Analysis:

Asymptotic Analysis of an algorithm refers to computing the running time of any operation in mathematical units of computation.

It is not perfect, but best way available for analyzing algorithms.

Using asymptotic analysis, we conclude the algorithm in three types:

  1. Best Case – Minimum time required for program execution.
  2. Average Case Average time required for program execution.
  3. Worst Case Maximum time required for program execution.

Asymptotic Notation

Asymptotic Notation are used to represent the complexities of algorithms for asymptotic analysis.

It is a standardized way of measuring how much memory an algorithm uses or how long it runs for given input.

Following are commonly used asymptotic notation are :

  1. Big-O Notation
  2. Omega-Ω Notation
  3. Theta-Θ Notation

Big-O Notation :

Big-O Notation refers to the upper bound of time or space complexity of an algorithm. It measures the worse case time complexity.

Big-O of g(n), written as f(n) = O(g(n))

figure : Big-O Notation

In the worst-case analysis, we calculate upper bound on running time of an algorithm.

Omega-Ω Notation :

Omega-Ω Notation refers to the lower bound of time or space complexity of an algorithm. It measures the best case time complexity.

Big-Omega of g(n), written as f(n) = Ω(g(n))

figure : Omega-Ω Notation

In the best-case analysis, we calculate lower bound on running time of an algorithm.

Theta-Θ Notation :

Theta-Θ Notation refers to the tight bound of time or space complexity of an algorithm. It expresses both the lower bound and upper bound of an algorithm’s running time.

Big-Theta of g(n), written as f(n) = Θ(g(n))

figure – Theta-Θ Notation

In average case analysis, we take all possible inputs and calculate computing time for all of its inputs.

Lower Bound <= Average Time <= Upper Bound
Code language: Markdown (markdown)

Growth Rate of Algorithm

Growth Rate of Algorithm is the rate at which the running time increases as a function of input.

O(1) < O(log2n) < O(n) < O(n2) …….. < O(nk) < O(2n)

log(n!) < (log(n))!

log(log*n) < log*(log n)

n < (log n)log n

2n < n! < nn

Here, list of growth rates are:

Time ComplexityNameExample
O(1)ConstantAdding an element to the front of a linked list
O(log n)LogarithmicFinding an element in a sorted array
O(n)LinearFinding an element in an unsorted array
O(n log n)Linear LogarithmicSorting n items by ‘divide-and-conquer’
O(n2)QuadraticShortest path between two nodes in a graph
O(n3)CubicMatrix Multiplication
O(2n)ExponentialThe Tower of Hanoi


Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.

Leave a Comment

Your email address will not be published. Required fields are marked *