Mathematical Foundation of Computer Science

DHARM

38 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

d 22 = ∑cckk′ 22 −

0

22

= (c 0 + c 1 + ..... + c 9 ) + c 10 + c 11

= (10.2) + 3.1 + 3.1 = (10.2) + 2.3

In general we can summarize the numeric function dn as,

d

n

nn

nn

n=

≤≤

−≤≤

+− ≥

R

S

|

T|

010

10 2 20

10 2 20 3 21

for 0

for 11

for

().

.( ).

2.3 Asymptotic Behavior (Performance) of Numeric Functions...........................................

Let an and bn are two numeric functions i.e.,
an = C 1 n^2 + C 2 n and
bn = C 3 n where C 1 , C 2 , and C 3 are constants
corresponding to the time taken by the two sorting algorithms to sort n numbers. Then we
compare the performance between two algorithms. Algorithm bn will be faster if n is suffi-
ciently large. For small value of n, either algorithm would be faster depending on constant C 1 ,
C 2 , and C 3. If C 1 = 1, C 2 = 2 and C 3 = 100 then C 1 n^2 + C 2 n ≤ C 3 n for n ≤ 98 and C 1 n^2 + C 2
n>C 3 n for n ≥ 99. If C 1 = 1, C 2 = 2 and C 3 = 1000 then C 1 n^2 + C 2 n ≤ C 3 n for n ≤ 998. Here our
point of interest is to see the behavior of the numeric functions an and bn with large value of n.
We observe that no matter what the constants are there will be a limit of n beyond that the
numeric function bn is faster then an. This limiting value of n is called threshold point. If
threshold point is zero, then bn is always faster or at least as fast than an. In fact exact thresh-
old point can’t be determined analytically. To handling this situation we introduce asymptotic
notations that create a meaningful observation over inexactness statements.
The asymptotic notation describes the behavior of the numeric functions that is, how the
function propagates for large values of n.
Fig. 2.2 shows some of the commonly used asymptotic functions that typically contain a
single term in n with a multiplicative constant of one.

Asymptotic Function Name

1 Constant

log n Logarithmic

N Linear

n log nn log n

n^2 Quadratic

n^3 Cubic

2 n Exponential

n! Factorial

1/n Inverse

Fig 2.2