Mathematical Foundation of Computer Science

DHARM

40 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

and b
n
n= n

=

=

R

S

T

0 024

135

for even)

1 for odd)

, , , ...... (

, , , ...... (

Then it is worthless to talk about asymptotic dominance among an and bn.

• It is also possible that, if | cn | ≤ C 1 | an | for n ≥ C 01 and | cn | ≤ C 2 | bn | for n ≥ C 02 ,
  then | bn | ≤/ C 3 | an | for n ≥ C 03 and | an | ≤/ C 4 | bn | for n ≥ C 04
  (where C 1 , C 2 , C 3 , C 4 , C 01 , C 02 , C 03 , C 04 are positive constants)
  For example,

a

n

n= n

=≥

=≥

R

S

T

13

3

for I or 3I + 1 (I 0)

0 for I + 2 (I 0)

and b n
n n
= =≥
=≥

R

S

T

13

3

for I or 3I + 2 (I 0)

0 for I + 1 (I 0)

and cn=RS n=≥
T

13 for I (I 0)
0otherwise
Then we see that both an and bn asymptotically dominates cn, i.e.,
| cn | ≤ 1. | an | for n ≥ 0(an asymptotically dominates cn)
(for C = 1, C 0 = 3I or 3I + 1 or otherwise C 0 ≥ 0, we have 1 ≤ 1. 1 or 0 ≤ 1. 0)
Similarly, | cn | ≤ 1. | bn | for n ≥ 0
(bn asymptotically dominates cn for C = 1 and C 0 ≥ 0)
Further we will see that an doesn’t asymptotically dominates bn. So, for any choice of C
& C 0 there exists a constant n 0 i.e.
n 0 ≥ C 0 and | bn 0 | = C. | an 0 |
Since C0 is zero so n 0 ≥ 0, therefore | bn 0 | ≥ | an 0 |. Likewise we would also see that bn
doesn’t asymptotically dominates an.

2.3.1 Big–Oh (O) Notation

Big–Oh notation is the upper bound; it bounds the value of the numeric function from above.
Let an be a numeric function then Big–Oh of an denoted as O(an) is the set of all numeric
functions bn that are asymptotically dominated by an, i.e.,
bn = O(an) ⇒ | bn | ≤ C | an | for n ≥ C 0
where C and C 0 are positive constants. Here symbol ‘=’ is read as ‘is’ not as ‘equal’. So the
definition states that numeric function bn is at most C times the numeric function an except
possibly when n is smaller than C 0. Thus numeric function an asymptotically dominant (an
upper bound) on bn for all suitably large values of n i.e. n ≥ C 0. O(an) is also read as ‘order of’ an.
For example,

• Let an = 3n + 2; since 3n + 3 ≤ 4 n for n ≥ 3, therefore an = O(n).


• Let an = 100n + 3; since 100n + 3 ≤ 100 n + n for n ≥ C 0 = 3, therefore an = O(n).
  Hence these numeric functions are bounded from above by a linear function for suit-
  ably large n.