Mathematical Foundation of Computer Science

DHARM

DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 39

To illustrate more, let numeric function, an = 7, for n ≥ 0 then its behavior remain
constant for increase in n. If an = 3 log n, for n ≥ 0 then behavior of numeric function is of
logarithmic nature for increase in n. For an = 5 n^3 , for n ≥ 0 then its behavior is cubic. For an =
7.2n, for n ≥ 0 then numeric function grows exponentially for increase in n. And for an = 2^5 /n,
for n ≥ 0 then function is diminishing for increase in n and finally approach to zero for large n.
Continue to the previous discussion of comparing the behavior of numeric functions, an
asymptotically dominates bn, if and only if there exist positive constants C and C 0 , i.e.
| bn | ≤ C | an | for n ≥ C 0
(Ignore the sign of numeric functions)
an asymptotically dominates bn signifies that an grows faster then bn for n beyond (the thresh-
old point) the absolute value of bn lies under a fixed proportion of absolute an. For example, let
an = n^2 , for n ≥ 0 and bn = n^2 + 5n, for n ≥ 0 then an asymptotically dominates bn for C = 2 and
C 0 = 5, i.e.
| n^2 + 5n | ≥ 2 | n^2 | for n ≥ 5
Consider another example let numeric functions are,
an = 2n, for n ≥ 0 and
bn = 2n + n^2 for n ≥ 0
Then an asymptotically dominates bn for C = 2 and C 0 = 4, i.e.,
| 2n + n^2 | ≤ 2 | 2n | for n ≥ 4
Alternatively we may say that bn doesn’t asymptotically dominates an, for any constants
C and C 0 , although there exists a constant n 0 i.e.,
n 0 ≥ C 0 and | an 0 | > C | bn 0 |
Latter in this section we will see the asymptotic dominance of numeric functions with
numeric function obtain after applying unary and binary operations.
(Assume an and bn are numeric functions)

• an ≤ C | an | for n ≥ C 0 (C and C 0 are positive constants)


• if | bn | ≤ C | an | for n ≥ C 0 then for any scalar k, | k bn | ≤ C | an | for n ≥ C 0


• if | bn | ≤ C | an | for n ≥ C 0 then | SI bn | ≤ C | SI an | for n ≥ C 0


• if | bn | ≤ C 1 | an | for n ≥ C 01 and | cn | ≤ C 2 | an | for n ≥ C 02 then for any scalar
  k and m,
  | k bn + m cn| ≤ C 3 | an | for n ≥ C 03
  (where C 1 , C 2 , C 3 , C 01 , C 02 , C 03 are positive constants and an, bn and cn are numeric functions)


• if | bn | ≤ C 1 | an | for n ≥ C 01 then also | an | ≤ C 2 | bn |
  for n ≥ C 02.
  (where C 1 , C 2 , C 01 , C 02 are positive constants)
  For example,
  an = n^2 + n + 1 and bn = 10–3 n^2 – n1/3 – 11 for n ≥ 0


• Conversely, if | bn | ≤/ C 1 | an | for n ≥ C 01 then also | an | ≤/ C 2 | bn | for n ≥ C 02.
  (where C 1 , C 2 , C 01 , C 02 are positive constants)
  For example,

a n

n n

=

=

R

S

T

1 024

135

for even)

0 for odd)

, , , ...... (

, , , ...... (