Data Structures Asymptotic Analysis - Data Structure & Algorithms

What is Asymptotic Analysis of an Algorithm?

Defining the mathematical boundation/framework of the run-time performance of an algorithm is defined as Asymptotic Analysis. Asymptotic analysis facilitates in identifying the best, average and the worst case scenario of an algorithm.

If input is not there for an algorithm, asymptotic analysis is concluded to work in constant time. All the other factors than input are considered constant.

In other words, the computing the running time of the operation in mathematical units of computation is referred as Asymptotic Analysis. For instance, the running time of one operation is computed as f(n) and may be for another operation it is computed as g(n2). This means the increase in n result in linear increase in the running time of the first operation and exponential increase in the running time of the second operation. If n is small, the running time of both of the operations will be almost same.

The time required by an algorithm falls under three types −

  • Best Case − Minimum time required for program execution.
  • Average Case − Average time required for program execution.
  • Worst Case − Maximum time required for program execution.

What are the commonly used Asymptotic Notations for an algorithm?

To calculate the complexity of an algorithm, the commonly used asymptotic notations are:

  • Ο Notation
  • Ω Notation
  • θ Notation

Big Oh Notation, Ο

The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. The worst case time complexity or the longest amount of time taken by an algorithm to complete is measured by notation Ο(n).

Big O Notation

For instance, for a function f(n)

Omega Notation, Ω

The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. The best amount of time an algorithm takes to complete is measured by notation Ω(n).

Omega Notation

For instance, for a function f(n)

Theta Notation, θ

The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time. It is represented as follows −

Theta Notation

What are the Common Asymptotic Notations used for an algorithm?

Some of the common asymptotic notations used most commonly are −

constant
Ο(1)
logarithmic
Ο(log n)
linear
Ο(n)
n log n
Ο(n log n)
quadratic
Ο(n2)
cubic
Ο(n3)
polynomial
nΟ(1)
exponential
2Ο(n)

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics