DHARM
DISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 41
Consider other numeric functions,
- Let an = 10n^2 + 2n + 2; since 10n^2 + 2n + 2 ≤ 10 n^2 + 3n for n ≥ 2. For n ≥ 3, 3n ≥ n^2.
Hence for n ≥ C 0 = 3, an ≤ 10 n^2 + n^2 = 11n^2. Therefore an = O(n^2 ).
- Let an = 3. 2n + n^2 ; since for n ≥ 4, n^2 ≤ 2 n. So, 3. 2n + n^2 ≤ 4. 2n for n ≥ 4, therefore
an = O(2n).
- Let an = 7, then an = O(1). Because an = 7 ≤ 7. 1, by setting C = 7 and C 0 = 0.
It is also observed that for an = 3n + 2 = O(n^2 ), because of 3n + 2 ≤ 3 n^2 for n ≥ 2. So, n^2 is
the upper bound (loose bound) for an. For an = 10n^2 + 2n + 2 = O(n^4 ), because of 10n^2 + 2n + 2
≤ 10 n^4 for n ≥ 2. Again, n^4 is not a tight upper bound for an. Similarly, for an = 3. 2n + n^2
=O(n^22 n) is a loose bound comparison to O(n 2 n) and further O(2n) is a tight bound for an.
It can also observe that an = 3n + 2 ≠ O(1), because there is no C > 0 and C 0 , i.e.
3 n+ 3 < C for n ≥ C 0. Similarly, an = 10n^2 + 2n + 2 ≠ O(n) and an = 3. 2n + n^2 ≠ O(2n).
Consider another example of numeric functions that are given as,
an = 3n + 2 ; bn = n^2 + 1 ; and cn = 9 ;
Then we formulate asymptotic relationship between the numeric functions that are
summaries as follows,
- an = O(bn), because for C = 1 and C 0 = 4, | an | ≤ 1. | bn | for n ≥ 4. Thus, bn asymptoti-
cally dominates an.
- cn = O(1), because for C = 9 and C 0 = 0, | cn | ≤ C. | 1 | or 9 ≤ 9.1 for n ≥ 0.
- cn = O(an), because for C = 1 and C 0 = 3, | cn | ≤ C. | an | or 9 ≤ 1.(3n + 2) for n ≥ 3.
Thus, an asymptotically dominates cn.
Also the order of the above numeric functions is given in the Fig 2.3 where column 1 of
the order shows the tight bound and rest of the column (2, 3, ..) shows loose bound for the
corresponding numeric functions.
Numeric Function Order
an = 3n + 2 O(n)O(n^2 )O(n^3 ), ......
bn = n^2 + 1 O(n^2 )O(n^3 )O(n^4 ), ......
cn = 9 O(1) — —
123
Fig. 2.3
Hence we reach to the following conclusions,
- an is O(bn).
- bn is not O(an) and nor O(cn).
- cn is O(1), but cn is not O(an), nor O(bn).
Reader must also note that when a numeric function bn is O(n log n), it means that bn
is asymptotically dominated by the numeric function n log n, let it be an. Thus, bn is O(an),
that is bn doesn’t grow faster than an, but it grow much slower than an. However, if bn is O(2n)
then it is rightly says that bn grows much slower than 2n.
