DHARMDISCRETE NUMERIC FUNCTIONS AND GENERATING FUNCTIONS 43or an ≤ {1/3} n^3 + O(n^2 )
Hence, an is {1/3} n^3 + O(n^2 ).
Example 2.23 Simplify the expression
{log n + O(1/k)}{k + O( k)} for any constant k.
Sol. Let an = {log n + O(1/k)}{k + O( k)}
= {k. log n + k.O(1/k) + log n. O( k) + O(1/k). O( k)}
= {k. log n + O(1) + log n. O( k) + O(1/ k)}
= {k + O( k)}. log n + {O(1) + O(1/ k)}
= C 1 log n + C 2 (where C 1 and C 2 are constants)
Therefore, an ≈ log n.
Example 2.24 Let an = loge n, show that an = O(ne) for e > 0.
Sol. Since, loge n ≤ ne for n ≥ e
Therefore, | an | ≤ 1. | ne | for n ≥ e, hence an is asymptotically denoted by ne.
Consequently, an = O(ne).
Example 2.25 Given a numeric function an, letb
a a a ...... a i for n 2
n 0forn 2
n n/2 n/4 n/2
i
= i
++++ =
≠R
S
T
if an = O( n), then show that bn = O( n log n).
Sol. For n = 2i given numeric function
bn = an + an/2 + an/4 + ......... + an/ 2 i
since an = O( n), therefore we have
bn = O( n) + O( n/2) + O( n/4) + ......... + O( n/2i)
= O( n). 1 + O( n). 1/ 2 + O( n). 1/ 4 + .........+ O( n). 1/ 2 i
= O( n). {1 + 1/ 2 + 1/ 4 + .........+ 1/ 2 i}
= O( n). {1 + (1/ 2 )^1 + (1/ 2 )^2 + .........+ (1/ 2 )i}
Find the sum and since n = 2i, so put i = log 2 n we get the required result, i.e.
bn = O( n log n)
Similar to the ‘Big–Oh’ notation other notations like Omega (Ω) and Theta (θ) are also
commonly used.
2.3.2 Omega (Ω) Notation.............................................................................................
Omega notation is the lower bound; it bounds the value of numeric function from below. Let an
be a numeric function then Omega of an denoted as Ω(an) is the set of all numeric functions bn
that grows at least as fast as an, i.e.,
bn = Ω(an)
It define as, | bn | ≥ C | an | for n ≥ C 0 , where C and C 0 are constant.
Alternatively, we can say that numeric function bn is at least C times the numeric func-
tion an except possibly when n is smaller than C 0. Thus, an is lower bound on the value of bn for
all suitably large n, i.e. n ≥ C 0.