Asymptotic Behavior Of Functions

Introduction: The time taken to execute any algorithm depends upon the machine on which it is implemented and also on the algorithm. Hence, efficiency of any algorithm is measured by the amount of time it takes and also the space it needs for execution on the machine. Comparison of algorithms has become an important topic. We give here a mathematical basis for comparing algorithms.

A complexity function f is a function of n, the size of the problem or parameter on which the problem is dependent. That is, f (n) is either a measure of the time required to execute an algorithm on a problem of size n or the measure of memory space. If f (n) is describing the measure of time, then f(n) is called the time-complexity function; if f(n) is describing the measure of space, then it is called space-complexity function.

We have the following important definitions of complexity functions.

Definition 1: Let f and g be two functions from N to R. Then g asymptotically dominates f or is an asymptotic upper bound for f or f is asymptotically dominated by g if there exist k ≥ 0 and c ≥ 0 such that f(n) ≤ cg(n) for all n ≥ k.

The set of all functions which are asymptotically dominated by a given function g is denoted by O(g) and read as ‘big-oh’ of g. That is f∊O(g), then f is said to be in O(g).

Example: Let f(n) = n, g(n) = n2. Then clearly f ∊O(g) as n ≤ 1.n2, whereas g ∉ O(f).

O(1) ⊂ O(logn) ⊂ O(n) ⊂ O(nlogn) ⊂ O(n2) ⊂ O(cn) ⊂ O(n!).

Definition 2: Let f and g be two functions from N to R. Then g is asymptotically tight bound for f(n) if there exist positive constants c1, c2 and k such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ k.

The set of all functions for which g is asymptotically tight bound is denoted by θ(g).

Example: If f(n) = an3 bn2 cn d, where a, b, c, d are constants and a >0. Then f(n) ∊θ(n3).

Definition 3:Let f and g be any two functions from N to R. Then g is said to be asymptotic lower bound for f if there exist positive constants c and k such that 0 ≤ cg(n) ≤ f(n) for all n ≥ k.

The set of all functions for which g is asymptotic lower bound is denoted by Ω(g).

Example:f(n) = an2 bn c, a, b, c, are constants, a > 0, belongs to Ω(n2).