A s y m p to ti c N o ta ti o n s and

Basic Efficiency Classes

n, th e ef fic ie nc y an al ys is fr am ew or k con-
io
~ s po in te d ou~ in th e previous sect m 's ba si c op er at io n co un t as th e
an al go ri th
centi;ates on th e or de r of growth of T o co m pa re an d ra nk su ch or de rs
's efficie nc y.
pr in ci pa l in di ca to r of th e algorithm : 0 . (b ig oh ), Q (big om eg a) , an d
e th re e no ta tio ns
of gr ow th , co m pu te r scientists us in fo r.m al ly ,-a nd th en , af te r sev-
e th es e no ta tio ns
0 (b ig th~ta). First, we-introduc e fo llo w in g di sc us si on , t( n) an d
e given. In th
er al ex am pl es , formal definitions ar th e se t of na tu ra l nu m be rs . In
nctions defin ed on
g( n) ca n be an y no nn eg at iv e fu m 's ru nn in g tim e (u su ally
will be an al go ri th
th e co nt ex t we ar e in te re st ed in, t( n) w ill be so m e si mple function
un t C (n ) ), an d g( n)
in di ca te d by its basic op er at io n co
to co m pa re th e co un t with.

In fo rm a l Introduction
l fu nc tio ns \V ith a sm al le r or sam e or de r of
In fo rm al ly , O (g (n )) is th e se t of al es to in fin ity). Th us , to give
m ul tip le , as n go
gr ow th as g( n) (t o within a co ns ta nt
 . of Algorithms
. & Analysis
the oesign
d ction to . ll true:
Intro u . assertwns are a 1 2
the fol low ing 2 -n (n - 1) E O( n ).
a few ex am ples. 2
2 JOOn + 5 E O( n ), d
n E O( n ),
d he n ce have a small·er or er of oto
0
~
. r an
linea dratic and hence has the same Ord
firs t tw o tunctwnst are
. er
h bil e the las on e IS qu a
Indeed , t e 2
d
(n) - n ' wthe oth er ban , 1 d. 0( 2) .
than g 2 0 n . 4
n n +n + 'F
row th as n . · 1
0000 3 d. O( n2 ),
g r/ O(n2), 0. n 'F
n3
3 ar e bo th cubic and henc e have a hi- g~
d 00 1n · 4
.
ns n an
3 O· ·
oo
th-deg re e po lyn om 1a 1n +· n +1.· ·
d , the functw . d ha s the fo ur fu ·
2
Indee ro wt h than n , an sO
s fo r the se t of all nct1ons with• a Ia r~t
d er O[g . n (g (n )) stand . •
or The second notat10 n, ,H, ,
t multiple, as n goes to Illfinj~
h as g( n) ( to wi thin a co ns tan
or same order of growt
For example,
1 , 2
bu t 10 0n + 5 ¢ !"l(n 2 ).
(n -"1 ) E Q( n ),
-n
2
the se t of all fu nc tions th at ~-av~ the same or de r of gro~
Finally, 0( g( n) ) is
lti~ le: as n go es to 1n fin1ty). Thus, ~v e~ quadra~
as g(-n) (to within a constant mu 2
2 + bn + c with a > 0 1s m 0( n ), but so ar
e, among mfinitely ma,
function an
(Can you explain wij.y?)
others, n2 + sinn and n + Iogn.
2
abi
pr ec ed ing inf or ma l :disc us sion has m ad e you comfort
_.Hopefully, the \
d the thr ee asym pto tic no tations. So now come the-form
with the idea behin ·
definitions.

O-notation
O(g(n))
on t(n ) is sa id to be in O( g( n) ), de no te d t(n ). E
~EFIN_ITION 1 A fun cti
me co ns tan t m ul tip le of g( n} fo r al l large n, i.e., ·
if t(n) 1s_bounded a~o_ve by so
t an d so me no nn eg ati ve ·in te ge r no such that
there exist some positive constan
c

no.
t(n) :S cg(n) for all n >
ur e 2 1 .. ,
is illu str ate d in Fi y, ni
The defin itio n
l nu mb er. g · wh ere , for the sake of visual clarit
extended to be a rea
.
ex am ple , let us f or mall . -
. As a~
e~ ro ve on e of th e assertions m ad e in t~1
mtroduction: 100n + 5 E O( n2 ). In d!
'
100n + 5 < 100n + n (fo r all n ~ 5) 101n < 101 n2 . =
Th as values of th - . - -
us, . .
e co ns tan ts c an d fin . t. aKI
101 a d 5 no re qu ire d by th e de we ca n t
n ' respectivefily. . . · I io n,
No te tha t the de .
d n n1 tio n giv es us a lot of fre '
m in choosing specific vaJue
for co nstan ts c an
o. Fo r ex am ple , we co uld l~ do
100 a ~0 reason that
5 '
n + :S lOO n + 5 n (fo r all n > 1)
. == lOSn -
to complete th th 10 --
e proof Wi c -
- 5 and no :::: 1.
 Fundamentals of the A
nalysis of Al . .
90nthm . ncy
Ett·rcre
- .
. 51

Cg(n)

t(n)

doe sn't I
mat ter '

FIGURE 2.1 s·1 h

9-0 notation: t(n) E O(g (n))

t(n)

cg(n)

doe sn't :
ma tter ,....- -
'I
I

I
I
I

Q(g (n))
FIGURE ~-2 Big -om ega notation: t(n) e

Q-notation
be in rl(g (n)) , denoted t(n) e Q(g(n)),
DEFINITION 2 A function t(n) is said to
e constant-multiple of g(n) for all large n,
if t(n ) is bou nde d bel ow by som e positiv
c and some nonnegative integer no such
i.e., if the re exi st som e positive constant
tha t ~ no.
t(n) > cg( n) for all n

Th e def init ion is illu stra ted in Figure 2.2: 2

3
is an exa mp le of the form al pro of tha t n e '2(n ):
He re
n3 > n 2 for all n ~ 0, T

i.e., we can sele ct c = 1 and no = 0.

a-n ot ati on ,, t(n) e 8(g(n)),

. "d b . E>(g(n.)) ~ denotedtant multiples of
to em ~
DEFINITION 3 A fun ctio n t(n) is sai ow by s?m e pos1t1ve cons
if t(n ) is bou nde d bot h abo ve and bel
 Introduction to t h e ue::, 1y1' ....... , .. ·- · , - ~

c 1 g(n)

.,,,.,.,.,.✓

~
I
I .
I

doesn't : ·
matter :
I
I
. I
I
L____ ___JI_ _ _ _ _ _ _ _ _ _. _ . n
no

FIGURE 2.3 Big-theta notation: t(n) E 8(g(n)) .

g(n)for all large n, i.e., if there exist s~me positive constant c1 and c2 and~
nonnegative integer no such that

c2g(n) < t(n) < c1g(n) for all n > no.

The definition is illustrated in Figure 2.3.

· For example, let us prove that ½n(n -- 1) E 8(n2 ). First, we prove ther
inequality (the upper bound):

1 21 1 1
2 n(n - 1) = -n
2
- -n < -n 2 for all n > 0.
2 - 2 -
Second, we prove the left inequality ( the lower ·b ound):

! n(n - 1) = 12n -
1 1 11 . 1 2
-n > -n 2 - -n-n (for all n > 2) == - n ·
2 2 2-2 . 22 - 4
Hence; we ·ccln select c2 = 14 , c1 -_ 1
, an
d _
no - 2.