We often want to know a quantity only approximately and not necessarily exactly, just to compare with another quantity. And, in many situations, correct comparison may be possible even with approximate values of the quantities. The advantage of the possibility of correct comparisons through even approximate values may be much less than the times required to find exact values. We will introduce five approximation functions and their notations.

The purpose of these asymptotic growth rate functions to be introduced, is to facilitate the recognition of essential character of a complexity function through some simpler functions delivered by these notations. For examples, a complexity function f(n) = 5004 n3 + 83 n2 + 19 n + 408, has essentially same behavior as that of g(n) = n3 as the problem size n becomes larger to larger. But g(n) = n3 is much more comprehensible and its value easier to compute than the function f(n)

Enumerate the five well - known approximation functions and how these are pronounced

1. The Notation O: Provides asymptotic upper bound for a given function. Let f(x) and g(x) be two functions each from the set of natural numbers or set of positive real numbers to positive real numbers.

Then f(x) is said to be O (g(x)) (pronounced as big - oh of g of x) if there exists two positive integers / real number constants C and k such that

F(x) ≤ C g(x) for all x ≥ k

2. The Ω Notation: The Ω notation provides an asymptotic lower for a given function.

Let f(x) and g(x) be two functions, each from the set of natural numbers or set of positive real numbers to positive real numbers.

Then f(x) is said to be Ω (g(x)) (pronounced as big - omega of g of x) if there exists two positive integer / real number constants C and k such that f(x) ≥ C (g(x)) whenever x ≥ k

3. The Notation : Provides simultaneously both asymptotic lower bound and asymptotic upper bound for a given function.

Let f(x) and g(x) be two functions, each from the set of natural numbers or positive real numbers to positive real numbers. Then f(x) is said to be (g(x)) (pronounced as big - theta of g of x) if, there exists positive constants C1, C2 and k such that C2 g(x) ≤ f(x) ≤ C1g(x) for all x ≥ k.

4. The Notation o: The asymptotic upper bound provided by big - oh notation may or may not be tight in the sense that if f(x) = 2x3 + 3x2 + 1. Then for f(x) = O(x3), though there exists C and k such that f(x) ≤ C(x3) for all x ≥ k yet there may also be some values for which the following equality also holds

f(x) = C(x3) for x ≥ k However, if we consider

f(x) = O(x4)

then there can not exits positive integer C such that

f(x) = C x4 for all x ≥ k

The case of f(x) = O(x4), provides an example for the notation of small - oh.

The notation o

Let f(x) and g(x) be two functions, each from the set of natural numbers or positive real numbers to positive real numbers.

Further, let C > 0 be any number, then f(x) = o (g(x)) (pronounced as little oh of g of x) if there exists natural number k satisfying

f(x) < C g(x) for all x ≥ k ≥ 1

5. The Notation ω:Again the asymptotic lower bound Ω may or may not be tight. However, the asymptotic bound ω cannot be tight. The definition of ω is as follows;

Let f(x) and g(x) be two functions each from the set of natural numbers or the set of positive real numbers to set of positive real numbers.

Further

Let C > 0 be any number, then f(x) = ω (g(x)) if there exists a positive integer k such that f(x) > C h(x) for all x ≥ k

Resources

Top Categories

Product

Company