Mathematical Foundation of Computer Science

DHARM

44 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

For example,

• Let an = 3n + 2, then 3n + 2 > 3n for n ≥ 0, therefore an = Ω(n).


• Let an = 100n + 3, then 100n + 3 > 100n for n ≥ 0, therefore an = Ω(n).
  Hence, above numeric functions are bounded from below by a linear function.
  Consider other numeric functions,


• Let an = 10n^2 + 2n + 2; since 10n^2 + 2n + 2 > 10n^2 for n ≥ 0, therefore an = Ω(n^2 ).


• Let an = 3. 2n + n^2 ; since 3. 2n + n^2 > 3. 2n for n ≥ 0, therefore an = Ω(2n).
  It is also observe that 3 n + 1 = Ω(1); 10n^2 + 2n + 2 = Ω(n); 10n^2 + 2n + 2 = Ω(1);

3. 2n + n^2 = Ω(n^100 ); 3. 2n + n^2 = Ω(n^2 ); 3. 2n + n^2 = Ω(n); and also 3. 2n + n^2 = Ω(1);
   But 3n + 2 ≠ Ω(n^2 ); We can prove this result by method of contradiction. Assume, 3n + 2 = Ω(n^2 )
   then there exist positive constants C and C 0 such that 3n + 2 ≥ C. n^2 for all n ≥ C 0.
   Therefore, C.n^2 /(3n + 2) ≤ 1 for all n ≥ C 0. This equality can’t be true because,
   C.n^2 /(3n + 2) grows faster and reaches to infinity for larger value of n. Therefore, C.n^2 /(3n+2)
   ≤/ 1. Hence, 3n + 2 ≠^ Ω(n^2 ).

2.3.3 Theta (θ) Notation................................................................................................

Theta notation is the average bound; it bounds the value of numeric function both from above
and below. Let an be a numeric function then theta of an denoted by θ(an) is the set of all
numeric functions bn such that there exist positive constants C 1 , C 2 , and C 0 , i.e.,
C 1. | an | ≤ | bn | ≤ C 2. | an | for n ≥ C 0
That can be written as, bn = θ(an)
It means, numeric function bn lies between C 1 times the numeric function an and C 2
times the numeric function an except possibly when n is smaller then C 0. Thus, an is both a
lower bound and an upper bound on the value of an for all suitably large n, i.e. n ≥ C 0. In other
words, bn grows similar as an. From the definition, it is also concluded that an is both Ω(bn) and
O(bn).
For example,

• Let an = 3n + 2; since 3n + 2 > 3n for n ≥ 0 and 3n + 2 ≤ 4 n for n ≥ 3. Combining these
  inequalities we have 3n ≤ 3 n + 2 ≤ 4 n for n ≥ 3. Hence, an = Ω(n) and an = O(n).
  Therefore an = θ(n).


• Let an = 10n^2 + 2n + 2; since 10n^2 ≤ 10 n^2 + 2n + 2 ≤ 11 n^2 for n ≥ 2. Therefore an = θ(n^2 ).


• Let an = 3. 2n + n^2 ; since 3. 2n ≤ 3. 2n + n^2 ≤ 4. 2n for n ≥ 4. Therefore an = θ(2n).
  Consider another numeric function an = 3 log 2 n + 5; since log 2 n < 3 log 2 n + 5 ≤ 4 log 2 n
  for n ≥ 32. Therefore an = θ(log 2 n).
  Previously we showed that 3n + 3 ≠ O(1), therefore 3n + 3 ≠ θ(1). Also we have shown
  that 3n + 2 ≠ Ω(n^2 ) so 3n + 2 ≠ θ(n^2 ). Since, 10n^2 + 2n + 2 ≠ O(n) therefore 10n^2 + 2n + 2 ≠ θ(n)
  and also 10n^2 + 2n + 2 ≠ θ(1).

Example 2.26 Let numeric functions an = 3n and bn = 2n for n ≥ 0, then show that

(i)Does an asymptotically dominates bn.

(ii)Does an*bn asymptotically dominates bn.

(iii)Does an*bn asymptotically dominates an.

Sol. (i) Numeric function an asymptotically dominates bn if there exists positive constants C

and C 0 i.e.,