Mathematical Foundation of Computer Science

DHARM

42 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

The features of asymptotic dominance of numeric function in terms of ‘Big–Oh’ nota-

tion is further states as follows, (let an, bn and cn are numeric functions)

• an is O(|an|).


• If bn is O(an) then also k.bn is O(an), for any scalar k.


• If bn is O(an) then also SI.bn is O(SI an), where I is any integer.


• If bn is O(an) and cn is O(an) then also k.bn + m cn is O(an), for any scalars k and m.


• If cn is O(bn) and bn is O(an) then cn is O(an).


• It is possible that if an is O(bn) then also bn is O(an). For example, the numeric
  functions, an = 3n^2 and bn = 2n^2 + 1, then an is O(bn) and bn is O(an).


• It is possible that if an ≠ O(bn) then also bn ≠ O(an). For example, the numeric func-
  tions, an = n^2 + 1 and bn = 3 log n, then an ≠ O(bn) and also bn ≠ O(an).


• It is possible that both cn is O(an) and cn is O(bn) but an ≠ O(bn) and also bn ≠ O(an).
  Example 2.21 Let an be a numeric function such that
  an = am nm + am–1 nm–1 + am–2 nm–2 + ............ + a 1 n + a 0 and am > 0, then show that an =
  O(nm).

Sol. Since, an ≤ (^) Σ
k
m
= 0
| ak | nk
≤ nm Σ 0
m
| ak | nk–m
≤ nm Σ 0
m
| ak | for n ≥ 1
Therefore, an = O(nm), or an is O(nm).
Example 2.22 Let an = 3n^3 + 2n^2 + n, then show asymptotic behaviors of an.
Sol. For given numeric function an = 3n^3 + 2n^2 + n, it is clear that,

• an is O(n^3 ) for n ≥ 3, because 3n^3 + 2n^2 + n ≤ 3 n^3 + n^3 or 2n^2 + n ≤ n^3 for n ≥ 3.
  
  
  • Also, an is 3n^3 + O(n^2 ) for n ≥ 2, because 2n^2 + n ≤ 3 n^2 for n ≥ 2.
  
  
  • And also, an is 3n^3 + 2n^2 + O(n) for n ≥ 0, because n ≤ 1.n for n ≥ 0.
    Hence, we summarize the behavior of the numeric function an as,
    {3n^3 + 2n^2 }+ O(n) < {3n^3 }+ O(n^2 ) < O(n^3 ).
  
  
  
  

Example 2.23 Let an = Σ

k

n

= 0

k^2

(i) Show an = O(n^3 ).

(ii) Show an = (n^3 /3) + O(n^2 ).

Sol. (i) We have, an = Σ
k

n

= 0

k^2 = 0^2 + 1^2 + 2^2 + ....... + n^2

= n(n + 1) (2n + 1)/6

or an = 1/3 n^3 + 1/ 2 n^2 + 1/6n

Since 1/3 n^3 + 1/2 n^2 + 1/6 n ≤ 2/3 n^3 for n ≥ 2

Therefore, | an | ≤ 2/3 | n^3 | for n ≥ 2, hence an = O(n^3 ).

(ii) Since, an = 1/3 n^3 + 1/2 n^2 + 1/6 n

so 1/3 n^3 + {1/ 2 n^2 + 1/6 n} ≤ 1/3 n^3 + {1/2 n^2 + 1/2 n^2 } for n ≥ 0

≤ {1/3} n^3 + n^2