Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

omega
bigoh
theta
communitycreator

Asymptotic notations and their properties

Buchiredddypalli Koushik

Asymptotic notations are used to analyze and determine the running time of an algorithm.

There are three main types of asymptotic notations:

  • Big-oh notation: Big-oh is used for upper bound values.
  • Big-Omega notation: Big-Omega is used for lower bound values.
  • Theta notation: Theta is used for average bound values.

Properties of Asymptotic Notation

General properties

  • If f(n) is Big-Oh(g(n)), then a*f(n) is Big-Oh(g(n))

  • If f(n) is Omega(g(n)), then a*f(n) is Omega(g(n))

Reflexive

  • If f(n) is given, then f(n) is Big-Oh(f(n))

Transitive

  • If f(n) is Big-Oh(g(n)) and g(n) is Big-Oh(h(n)), then f(n)=Big-oh(h(n))

Example

f(n)=ng(n)=n2andh(n)=n3f(n)=n g(n)=n^2 and h(n)=n^3

then n=Bigoh(n2)n = Big-oh(n^2) n2=Bigoh(n3)>n=Bigoh(n3)n^2 = Big-oh(n^3) -> n = Big-oh(n^3)

Symmetric

If f(n) is theta(g(n)), then g(n) is theta(f(n))

Suppose f(n)=n2;g(n)=n2f(n)=n^2; g(n)=n^2

f(n)=theta(n2)f(n)=theta(n^2)

g(n)=theta(n2)g(n)=theta(n^2)

Transpose symmetric

If f(n) = Big-Oh(g(n)), then g(n) is Omega(f(n))

Example

f(n)=nf(n)=n and g(n)=n2g(n)=n^2

Tmhen n is bigoh(n2)big-oh(n^2) and n2n^2 is omega(n)omega(n)

RELATED TAGS

omega
bigoh
theta
communitycreator

CONTRIBUTOR

Buchiredddypalli Koushik
RELATED COURSES

View all Courses

Keep Exploring