Asymptotic Notations

Asymptotic Notations

The Asymptotic behaviour of a function f(n) refers to the growth of f(n) as n gets larger. We typically ignore the small values of n since we’re usually interested in estimating how slow the program will be on large inputs.

Ø The Θ Notation:

The Θ Notation bounds a function from above and below, so it defines exact asymptotic behaviour of the function f(n)=Θg(n) if and only if there exists positive constants c₁, c₂, n₀ such that c₁g(n)≤f(n)≤c₂g(n) for all n≥n₀.

For example, we consider the following expression:

3n³ + 6n² + 6000 = Θ(n³). Dropping lower order terms is always fine because there will always be a n₀ after which Θ(n³) has higher values than Θn²) irrespective of the constants involved.

Ø The O Notation:

The O Notation bounds a function only from above, hence if defines an upper bound of an algorithm. The function is f(n)=Og(n) ) if and only if there exists positive constants c, n₀ such that f(n)≤cg(n) for all n≥n₀.

Example: we consider the following expression:

3n³ + 6n² + 6000 = O(n³).

Ø The Ω Notation:

Ω provides an asymptotic lower bound of a function. This notation can be useful when we want to compute the lower bound on the time complexity of an algorithm. The function is f(n)=Ωg(n) if and only if there exists positive constants c, n₀ such that cg(n)≤ f(n) for all n≥n₀.

Example: we consider the following expression:

3n³ + 6n² + 6000 = Ω(n³).