Asymptotic Notations

Asymptotic Notations

• To choose the best algorithm, we need to check efficiency of each algorithm. The efficiency can be measured by computing time complexity of each algorithm. Asymptotic notation is a shorthand way to represent the time complexity.

• Definition : Asymptotic notations are mathematical tools used in algorithm analysis to describe the running time or space requirement of an algorithm in terms of input size (n).

• Using asymptotic notations we can give time complexity as "fastest possible", "slowest possible" or "average time".

Various notations such as Ω Ө, and O used are called asymptotic notions.

 

1. Big oh Notation

• The Big oh notation is denoted by 'O'. It is a method of representing the upper bound of algorithm's running time. Using big oh notation we can give longest amount of time taken by the algorithm to complete.

Definition

• Let f(n) and g(n) be two non‒negative functions.

• Let n₀ and constant c are two integers such that n₀ denotes some value of input and n > n₀. Similarly c is some constant such that c > 0. We can write

f(n) ≤ c*g(n)

then f(n) is big oh of g(n). It is also denoted as f(n) ϵ O (g(n)). In other words f(n) is less than g(n) if g(n) is multiple of some constant c.

Example : Consider function f(n) = 2n + 2 and g(n) = n². Then we have to find some constant c, so that f(n) ≤ c* g(n). As f(n) = 2n + 2 and g(n) = n² then we find c for n = 1 then

f(n) = 2n+ 2

       = 2(1) + 2

f(n) = 4

and

g(n) = n²

        = (1)²

g(n)  = 1

i.e.

f(n) > g(n)

If n = 2 then,

f(n) = 2(2) + 2

       = 6

g(n)  = (2)²

g(n) = 4

i.e.

f(n) > g(n)

If n = 3 then,

f(n) = 2(3)+2

       = 8

g(n)  =  (3)²

g(n) = 9

i.e.

f(n) < g(n) is true.

Hence we can conclude that for n > 2, we obtain

f(n) < g(n)

Thus always upper bound of existing time is obtained by big oh notation.

2. Omega Notation

• Omega notation is denoted by 'Ω'. This notation is used to represent the lower bound of algorithm's running time. Using omega notation we can denote shortest amount of time taken by algorithm.

Definition

A function f(n) is said to be in Ω (g(n)) if f(n) is bounded below by some positive constant multiple of g(n) such that

  f(n) ≥ c* g(n)

For all n ≥ n₀

It is denoted as f(n) ϵ Ω (g(n)). Following graph illustrates the curve for  Ω notation.

Example :

Consider f(n) = 2n² + 5 and g(n) = 7n

Then if        n = 0

               f(n) = 2(0)² +5

                      = 5

               g(n) = 7 (0)

                      = 0              i.e. f(n) > g(n)

But if          n = 1

               f(n) = 2(1)² +5

                     = 7

              g(n) = 7(1)

                     = 7               i.e. f(n) = g(n)

If n = 3 then,

              f(n) = 2(3)² +5

                    = 18+ 5

                    = 23

             g(n) = 7(3)

                    = 21

i.e.          f(n) > g(n)

Thus for n > 3 we get f(n) > c* g(n).

It can be represented as

 2n²+5 ϵ Ω (n)

Similarly any

 n³ ϵ Ω (n)²

 

3. Ө Notation

• The theta notation is denoted by Ө. By this method the running time is between upper bound and lower bound.

Definition

• Let f(n) and g(n) be two non negative functions. There are two positive constants namely c₁ and c₂ such that

c₁ * g(n) ≤ f(n) ≤ c₂ * g(n)

Then we can say that

f(n) ϵ Ө (g(n))

Example :

If f(n) = 2n + 8 and g(n) = 7n.

where           n ≥  2

Similarly f(n) = 2n + 8

               g(n) = 7n

i.e.        5n < 2n + 8 < 7n        For n ≥ 2

Here     c₁ = 5    and               c₂ = 7 with n₀ = 2.

The theta notation is more precise with both big oh and omega notation.

 

Example: 1

Show the following equalities are correct.

i) 5 n²‒6 n = Ө (n²)

ii) n! = O(nⁿ)

iii) n³ + 10⁶n² = Ө (n³)

iv) 2 n² 2ⁿ+n log n = Ө (n² 2ⁿ)

Solution :

i) 5 n²‒ 6 n = Ө (n²)

The given function f(n) ϵ Ө (g (n)) only when f(n) can be represented as

c₁ * g(n) ≤ f(n) ≤ c₂ * g(n)

f(n) = 5 n²‒ 6 n. This can be denoted as n² ≤ 5 n²‒ 6 n ≤ 5 n² for all n ≥ 2.

Where g(n) = n², c₁ = 1 and c₂ = 5. Hence given equality holds true.

ii) n! = O(nⁿ)

The given function f(n) ϵ  O (g(n)) only

when               f(n) can be represented by

                        f(n) ≤ c * g(n).

Here                f(n) = n!   and      g(n) = nⁿ

The equation can be represented as,

 n.(n − 1).(n − 2) ....1 ≤ n . n . n .    ...n                    for all n≥1

This shows that f(n) ≤ c*g(n)                  where c = 1.

Hence given equality holds true.

iii) n³+10⁶n² = Ө(n³)

The given function is f(n) ϵ Ө (g (n)), only

when            f(n) can be represented as

c₁ * g (n) ≤ f(n) ≤ c₂ * g (n).

f(n) = n³ + 10⁶ n², f(n) = n³.

This can be denoted as ‒

n³ ≤ n³ + 10⁶ n² ≤ 10⁷n³

and        c₁ = 1, c₂ = 10⁷                                    for all n ≥ 1

Hence given equality is true.

iv) 2 n² 2ⁿ + n log n = Ө (n²2ⁿ)

The given function f(n) ϵ Ө (g(n)), only

when         f(n) can be represented as

c₁* g (n) f(n) ≤ c₂ * g(n).

f(n) = 2 n² 2ⁿ + n log n. This can also be denoted as ‒

c₁n² 2ⁿ ≤ 2 n² 2ⁿ + n log n ≤ c₂ n² 2ⁿ

 c₁ ≤ 2 +  ( n log n / n²2ⁿ)    ≤ c₂

where            for all n ≥ 1, 0 ≤ ( n log n / n²2ⁿ) ≤ 1

with              c₁ = 2, c₂ = 3 and n₀ = 1

Hence given equality is true.

Example: 2

State whether following equality is correct or wrong?

 5n³ + 4 n = Ω(n²)

Solution :

To prove that given function f(n) ϵ Ω(g(n)), only when f(n) can be represented as f(n) ≥ c * g(n) where n ≥ n₀.

Here, assume, f(n) = 5n³ + 4 n and g(n) = n².

 5n³ + 4n  ≥ n²         when c = 1, n₀ = 0

 for all n ≥ n₀. This shows that given equality is true.

Example: 3

State whether following equality is correct or wrong?

10n³ + n log n + 9 = O(n²).

Solution :

We assume that, we have obtained the values of c n₀ in such a way that n >= n₀ and we have 10n³+ n log n + 9 < c n². Now Let, m = max(n₀, ceiling (c/10)), then

We have,

10 m³ + m log m + 9 < cm²

         = 10 m³+ m log m + 9 − cm² < 0

         = m²(10 m ‒ c) + m log m + 9 < 0

But 10 m ‒ c > 0, hence

m²(10 m ‒ c) + m log m + 9 < 0 is not possible.

That means there are no such values of c and n₀ such that n ≥ n₀ and

10 n³ + n log n + 9 < c n². Hence given equality is wrong.

Example: 4

Derive a loose bound on the following equation:

f(x) = 35x⁸ ‒ 22x⁷ +14x⁵ ‒2x⁴ ‒4x²+x‒15

Solution :

Let, f(n) and g(n) are two non‒negative functions.

Let c be some constant.

The equation

                  f(n) ≤ c*g(n)

then          f(n) = ϵ O(g(n) with tight bound.

But if       f(n) < c*g(n)

then         f(n)  ϵ O(g(n) with loose bound.

Consider the function

          f(x) = 35x⁸‒22x⁷ +14x⁵ ‒2x⁴ ‒4x² +x‒15

and          g(x) =  x⁸

If                  x = 1, then

                 f(x) = 35(1)⁸ − 22(1)⁷ +14(1)⁵ −2(1)⁴ −4(1)² +1‒15

                  f(x) = 7

                 g(x) = x⁸ = (1)⁸

If we assume c = 35 then

We will always get

f(x) < g(x) for x ≥1

 

4. Basic Efficiency Classes

• We can have different efficiency classes and each class possessing certain characteristic. Let us see the classification of different order of growth 

Review Questions

1. Elaborate on asymptotic notations with examples.

2. Prove that for any two functions f(n) and g(n), we have f(n) f(n) = Ө(g(n)) if and only if f(n) = O (g(n)) and f(n) = Ω (g(n)).

3. Discuss in detail all the asymptotic notations with examples.

4. Give the definition and graphical representation of O‒notation.

5. Explain briefly Big oh Notation, Omega Notation and Theta Notations. Give examples.

6. What are the rules of manipulate Big ‒ oh expressions and about the typical growth rates of algorithm?

7. Define Big O notation, Big Omega and Big Theta notation. Depict the same graphically and explain.