Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

(Martin Jones) #1

CHAP. 3] FUNCTIONS AND ALGORITHMS 59


Rate of Growth; BigONotation


SupposeMis an algorithm, and supposenis the size of the input data. Clearly the complexityf (n)ofM
increases asnincreases. It is usually the rate of increase off (n)that we want to examine. This is usually done
by comparingf (n)with some standard function, such as


logn, n, nlogn, n^2 ,n^3 , 2 n

The rates of growth for these standard functions are indicated in Fig. 3-7, which gives their approximate values
for certain values ofn. Observe that the functions are listed in the order of their rates of growth: the logarithmic
function log 2 ngrows most slowly, the exponential function 2ngrows most rapidly, and the polynomial functions
ncgrow according to the exponentc.


Fig. 3-7 Rate of growth of standard functions

The way we compare our complexity functionf (n)with one of the standard functions is to use the functional
“bigO” notation which we formally define below.


Definition 3.4: Letf(x)andg(x)be arbitrary functions defined onRor a subset ofR. We say “f(x)is of order
g(x),” written
f(x)=O(g(x))
if there exists a real numberkand a positive constantCsuch that, for allx>k, we have


|f(x)|≤C|g(x)|

In other words,f(x)= 0 (g(x))if a constant multiple of|g(x)|exceeds|f(x)|for allxgreater than some
real numberk.
We also write:
f(x)=h(x)+O(g(x)) when f(x)−h(x)=O(g(x))
(The above is called the “bigO” notation sincef(x)=o(g(x))has an entirely different meaning.)
Consider now a polynomialP(x)of degreem. We show in Problem 3.24 thatP(x)=O(xm).
Thus, for example,


7 x^2 − 9 x+ 4 =O(x^2 ) and 8x^3 − 576 x^2 + 832 x− 248 =O(x^3 )

Complexity of Well-known Algorithms


Assumingf(n) andg(n) are functions defined on the positive integers, then

f (n)=O(g(n))

means thatf (n)is bounded by a constant multiple ofg(n)for almost alln.
To indicate the convenience of this notation, we give the complexity of certain well-known searching and
sorting algorithms in computer science:


(a) Linear search:O(n) (c) Bubble sort:O(n^2 )
(b) Binary search:O(logn) (d) Merge-sort:O(nlogn)
Free download pdf