idiJ Algorithms vs Programs

Algonthrns can be contrasted with programs. Algorithms. like blueprints that deals with large-scale software development Pro· ct
· · Je mana
that are used for constructing a house, help solve a given problem issues such as team management, extensive planning _9ernel'lt
. t h d . , cost estin,<11;..
logically. A program is an expression of that idea, consisting of a set an d proiec sc e uhng are the main focus of software . ~'"JI\
engine . ,
of instructions written in any programmi ng language. The develop- 0 n the other hand, algorithm design and analysis as a fi Id eru1g.
ment of algorithms can also be contrasted with software development. take a micro view of program development. Its focus . iet of study
. . is o deve•-
At the industrial level, software development is usually undertaken by effi cIent algonthms for basic tasks that can serve as a bu'ld' 11JP
a team of programmers who develop software, often for third-party for various app Icat1ons. Often project management issues iofing bin..,.
. 1· .
v""
customers, on a commercial basis. Software engineering is a domain development are not relevant to algorithms. SOftware

Finiteness An algorithm should have a finite number of steps and should terminate after executing the finite set of i
0st
tions. Therefore, finiteness is an important characteristic of an algorithm. ruc.
Some of the addit ional characteristics that an algorithm is supposed to possess are the following:

Simplicity Ease of implementation is another important characteristic of an algorithm.

Generality An algorithm should be generic, independent of any programming language or operating systems, and able t
0
handle all ranges of inputs; it should not be written for a specific instance.

An algorithm that is definite and effective is also called a computational procedure. In addition, an algorithm should be
correct and effic ient, that is, should work correctly for all valid inputs and yield correct outputs. An algorithm that executes fast
but gives a wrong result is useless. Thus, effic iency of an algorithm is secondary compared to program correctness. However
if many correct soluti ons are available for a given problem, then one has to select the best solution (or the optimal solution)
based on factors such as speed, memory usage, and ease of implementation.

1.5 NEED FOR ALGORITHM EFFICIENCY

Computer resources are limited. Hence, many problems that require a large amount ofresources cannot be solved. One good
example is the travelling salesperson problem (TSP). Its brief history is given in Box 1.6.
A TSP is illustrated in Fig. 1.2 . It can be modelled as a graph. A graph consists of a set of nodes and edges that interconnect
the nodes. In this case, cities are the nodes and the paths that connect the cities are the edges. Edges are undirected in this
case. Alternatively, it is possible to move from a particular city to any other city. The complete details of graphs are provided
in Chapter 5. A TSP involves a travelling person who starts
from a city, visits all other cities only once, and returns to
0
(a)
the city from where he started.
A brute force technique can be used for solving this
problem. Let us enumerate all the possible routes. For a
A 1----- - - - - - - - - < B TSP involving only one city, there is no path. For two cities,
there is only one path (A-B). For three cities, there are two
paths. In Fig. 1.2, these two paths are A-B-C and A-C-8,
assuming that A is the origin from where the travelling sales-
C
(c)
person started. For four cities, the paths are {A- D-B-C-A,
(d)
A- D-C- 8-A, A- B-C- D-A, A- B- D-C- A,A-C- D-B-A,
Fig. 1.2 Travelling salesperson problem (a) One city-no path and A-C-D- B- A}.
(b) Two cities (c) Three cities (d) Four cities

tm] History of travelling salesperson problem

A travelling salesperson problem (TSP) is one of the most impor- called vertices. The objective is to find a tour starting from a city, visit~
tant optimization problems studied in history. It is very popular among ing all other cities only once, and finally returning to the city where the
computer_s_c1enlists. It was studied and developed in the 19th century tour started. This is called a Hamiltonian cycle. The TSP is to find a
by Sir W1ll1am Rowan Hamilton and Thomas Pennington Kirkman. Hamiltonian cycle in a graph. The problem was then studied extensively
In 1B57 . Hamilton created an lcoslan game, a pegboard with 20 holes by Karl Menger in Vienna and Harvard later in the 1930's.
 l11trr11 /11 ,.tir111 to 1llw1rithm.v 7

Table 1.2 Compl(~'l!ily or TSP Thus. cvcry add ilio 11 or a cily can he 11n1cd to increase the rath ex ponent
ial ly.
[ Numbor of cities 'j Number of routes
Tnbk 1.2 shows 1hc nun1hc r or pnss ibk ro11lcs.
Therefore, it ca n be observed th at, l'or N cities, the number of route<;
0 (os there ls no route)
wo uld
,
I ,

be (N - 1)I fo r N ~ 2. The ava il ability or an algorith m for a prohle

m docs not
mean that the problem is solvable by a computer. There arc rminy prohl
ems that
3 2 cannot be solved by a computer and fo r many problem s algorithms
I 4
require a
6 huge amount or resources that cannot be prov ided practica ll y. For
exampl e, a
5 24 TS P cannot be solved in rea lity. Wh y? Let us ass ume that there arc
I 00 c1t1c'l.
6 120 As N = I00, the possibl e ro utes are then ( I00 - I)! = 99! .
The value or the numbe r 50! is 304 1409320 I7133780436 12608 I660647
688
443 7764 15689605 12000000000000. There fo re, 99! is a very large nu
eve n if a computer takes one second to r exploring a route, the algorith mber, and
m will run fo r years, which is plainly not acceptable.
Just imagin e how much time this algorithm will require, if the TSP
is tried out fo r all cities of India or USA. Thi s shows that
the deve lopment of efficient algori thms is very import ant as computer
resources are often limited.
1.6 FUNDAMENTAL STAGES OF PROBLEM SOLVING
Effi cient problem solving is both an art and a science. The problem-solvin
g process starts
with the understanding of a given problem and ends with the programming
Problem
code of the given
problem. The stages of problem solving are shown in Fig. 1.3.
The fo llowing are the stages of problem solving :
I . Understanding the problem 5. Analysing an algorithm
2. Planning an algorithm 6. Implementing an algorithm
3. Designing an algorithm 7. Performing empiri cal analysis
4. Validating and verifying an algorithm (if necessary)
Algorithm design
1.6.1 Understanding the Problem
The study of an algorithm starts with the computability theory. Theore
tically, the primary
question of computability theory is the following: ls the given problem
Algorithm validation solvable? Therefore,
a guideline for problem solving is necessary to understand the problem
fully. Hence, a proper
\------- --- - -- --- - -- problem statement is required. Any confusion regarding or misunderstand
ing of a problem
' statement will ultimately lead to a wrong result. Often, solving the
numerical instances of
Algorithm analysis a given problem can give an insight to the problem. Similarly, algorith
mic solutions of a
related problem will provide more knowledge for solving a given algorith
·--- - ---- - - - - -- - ---- m.
Generally, computer systems cannot solve a problem ifit is not properly defined
. Puzzles often
Implementation and fall under this category, which needs supreme level of intelligence. These
problems illustrate the
empirical analysis limitations of computing power. Humans are better than computers in
solving these problems.
.- - - - - - - - - - - - - - - - - - -
1.6.2 Planning an Algorithm
Post analysis The second important stage of problem solving is planning. Some of
the important decisions
are detailed in the following subsections.

Model of Computation
A computation model or computational model is an abstraction
of a real-wo rld comput er.
A model of computation is a theoretical mathematical model and does
not ex ist in phys i-
cal sense. It is thus a virtual machine, and all programs can be execute
d on this virtual
machin e theoretically. What is the need for a computing model? It
is meanin gless to talk
about the speed of an algorithm as it varies from machin e to mac hine.
An algorithm may
run faster in machin e A compared to in machin e B. This kind of analysi
Fig. 1.3 Stages of
s is not correct as
algorithm analys is should be independent of machin es. A comput ing
problem solving
model thus fac ilitates
such machin e-independent analysis.
 putability the
t is u_s e~ widely in com
j:r §i ) Alan Turing the Turing machi~e tha dite d with the d _ory allu
contr,bulion 1owa s
rd n Turrng ,s also cre
4) Is well known for his complexity ana lysis. Ala lligence of es,gl'lif'lg 01
(1 9
· 12 195 asure of tes ting the inte a niac n·'~ti
Ala n Tur ing
ored by many os the 'fa
ther of mo den ; the 'Turing Test' as a me
computing Ho Is consid theory a~d artlficia
n towards computablhty
rom puling·. His contributio ed o theore tical rnacliine, ca lled
al. He des ign
Intelligence Is monument

Fu el station

Queue of trucks

sn~
-=~ ~ ~ ~~
~~ ~~~~ ~
Fig. 1.4 Example of a queue

ns he lp specify th•
n sho uld be spe cif ied . Th ese va lid op era tio
tions of the mo del of co
mp uta tio ute time an;
First. all the \ a lid op era vid e a no tio n of the ne ce ssa ry st ep s to co mp
ng mo de ls pro
t. ln add itio n, the co mp uti . . .
inp ut. pro ces s, an d outpu ch m~ IS use d to perform
of a give □ alg ori thm . ine (R AM ) or a Tu rm ? ma
spa ce co mp lex itie s a ran do m acc ess ma ch ter 18. The
mp utation mo del suc h as s are dis cu sse d m Ch ap
Fo r alg ori thm study, a co d in Ch ap ter 3 an d Tu rin g ma ch ine
ori thm s. RA M is dis cu sse de ls (re fer to Bo x 1. 7).
co mp lex iry an aly sis of alg the stu dy of co mp uta bil ity an d co mp uti ng mo
g is vital for
co ntr ibution of Alan Tu rin
m
for so lvi ng a giv en proble
Da ta Organization ati on shi ps are sto red . Al go rit hm s req uir e da ta ori thm s and data
the wa y dat a and its rel ori thm s. T he ref ore , alg
Data str uct ure co nc ern s can ha ve im pa cts on the eff ici en cy of alg
ir organi zat ion
Th e nat ure of dat a and the ect of pro ble m sol vin g. ple of da ta organization
ure s tog eth er oft en co nst itu te an im po rta nt asp life . Fig ure 1.4 sh ow s an ex am
str uct wi th in ou r da i ly
av oid ch ao s. A que ue
eth ing we are fam ilia r sh ow n in the fig ure , to
Data org an iza tio n is som int sho uld ha ve a qu eu e, as
an d a vehicle
lle d a qu eue . A ga s sta tio n wi th on e ser vic ing po ce ssi ng (fi llin g of ga s) is do ne at on e en d
ca n wh ere the pro
(FI FO )) is an org an iza tio the ch oic e of structures.
(o r Fir st- in -Fi rst -O ut in thi s cas e. Of ten a pro ble m dic tat es
Al l ve hic les ha ve sam e
pri ori ty hig he st priori~
is ad ded at the oth er e □ d. ple , ha nd lin g me dic al em erg en cie s, wh ere
of, for ex am
ma y no t be va lid in cas es
Ho we ver , this str uc tur e int of problem solv-
sho uld be giv en to urg en
t cas es.
s the eff ect ive nes s of alg ori thm s. At so me po
a very important issue tha
t inf lue nce 'algorithm +
Thus, data organization is ly. A po pu lar sta tem en t in co mp ute r sci en ce is
the dat a effective
sho uld be g iven to sto rin g al in the pro ble m- sol vin
g pro ces s.
ing. carefu l con sideration str uct ure oft en pro ve s fat
A wr on g selection of data
data structu re = program '.
1.6.3 Designing an Algorithm ry iss ue s of thi s sta ge :
ble m sol vin g. Th e fol low ing are the tw o pri ma
t sta ge of pro
Algo rithm design is the nex ori thm ? ·
n an alg ori thm ? 2. Ho w to ex pre ss an alg
1. Ho w to de sig
str ate gie s dimr
s usi ng an ap pro pri ate de sig n str ate gy. De sig n I it i•
uti on
thm des ign is a wa y o~ dev ~lo pin g al~ ori thm ic sol ho ne dir ect ory If an yo n t.rt
sea rc
h.
mg
fr
om pa ge , ~·
ti Alg ori rch ing a na me in a tel ep · esa s ·
Jus t 1m ag 111e sea .
ram problem to problem. s· k
d1rectory is ind ex ed ' it ma es sen se to op en the bo ok an d us e the
mdex al
ter me d as a b ru Ie fiorc e str ate gy. mc e a tel ep ho ne · d. • stu dy .
S e PI
om
is is a bet ter str at. g me acr oss ma ny de s alg ori thm
top tu locate the name. Th e y. O ne ma ydco . ign pa ra 1gms m the d . 'd sih<
div ide and co d mm ing D' ·d d for ex am ple , IVl e ·.
gm s are am 1c pro gra . 1v1 e an co fth nq ue r,
the im portant design paradi nq ue ran yn b bl . · ven pro ble m. DynaJ 111,•
bl lem s and co mb ine s th e res ults of th -pr o em s to ge t the fin al so Iu t·ion o e g1
pro em into su b-prob . s the pro ble m as a seque nce of d . .
e su . . sub -pr ob lems r,
. vis
1ng
. ualize
Th en it co mb ine s the op tim al sol uti on s of the
prc,grnmm eci sio ns.
 /11tmr/11r l inn 111 Alxori1hm1· 9

get an 0p1imal glnhal s1,hll 1l,11 . rv1a11 y design ,·nri:,nl s Sllch as greedy nppn1:H.:h. hackt ruck 111g, anu bra nch nnd bound tec hn iq ues
ha, c hrcn den II \\ nh 111 th is bl,l'J,, Thl' n,k or alg(ll ithm dcsl).!.II is inipmt nnt 111 developing clli cient algorithms. Thu~, one impor-
tant skill rcq11in.', d 1~,1 p1\,hkm ~ll h 111 g. 1~ the sckction ,llld appli ca tion of' suit nblc de~ ign pHradi gms. /\ ~killed algorith m designer
1~ ralkd .m 'nlg11nst' .

Algorithm Specification
A1k r the :i ll_!nri thm i~ dl.'si gncd, ii shnuld be commu ni cnted lo a programmer so that the algo rithm can be coded as a program .
Thi s stag1.' 1s l.'.,1lkd algo,-irhm specifirn 1io 11 . Onl y three possibilities exist for com muni cat in g the idea of algo rithms. One is to
use na1ur,1l languages sud1 ns English to co mmuni cate th e algorithm . This is preferable. However, the natural language has
$o.11lW di ~:ld \ anta g:t'S such as ambigui ty and lack of precision. Hence, an algorithm is ofte n written and communi cated through
psl.'11d0l'l1dc. Pseud oc0dc is a mix of the natura l language and mathematics. Another way is to use a programming language.
Tiie pn,bkm \\ ith programming language notation is that readers often get bogged clown by the programming code details.
Therefore. the pseud ocode approach is preferable. Even though there are no specific rules for algorithm writing, certa in
guidel ines c:in be fo ll owed to make algorithms more understa ndable. Some of these guidelines are presented in Chapter 2.

1.6.4 Validating and Verifying an Algorithm

Algorith m validation and verification are the methods of checking algorithm correctness. An algorithm is expected to give
correct outputs for all valid inputs. Sometimes, algorithms may not give correct outputs due to logical errors. Hence, validation
of algorithms becomes a necessity. Algorithm validation is a process of checking whether the given algorithm gives correct
outputs for va li d inputs or not. This is done by comparing the output of the algorithm with the expected output.
Once va lidation is over, algorithm verification or algorithm proving begins. Algorithm verification is a process of providing
a mathematical proof that the given algorithm works correctly for all instances of data. One way of doing it is by creating a
set of assertions that are expressed using mathematical logic. Assertions are statements that indicate the conditions of algo-
rithm variab les at various points of the algorithm. Preconditions indicate the conditions or variables before the execution of
an algorithm, and postconditions indicate the status of the variables at the end of the execution ofan algorithm. Remember,
still the algorithm has not been translated or converted into a code of any programming language. Hence, all these executions
are first carried out theoretically on paper and proof for the algorithm is detennined. A proof of an algorithm is said to exist
if the preconditions can be shown to imply the postconditions logicall y. A complete proof is to write each statement clearly
for proving that the algorithm is right. In addition to assertions, mathematical proof techniques such as mathematical induc-
tion can be used for proving that algorithms do work correctly. Mathematical induction is one such useful proof technique
that is often used to prove that the algorithm works for all possib le instances. Mathematical proofs are rigorous and always
better th an algorithm validation. Program correctness itself is a major study area and extensive research is done in this field .
1.6.5 Analysing an Algorithm
In algorithm study, complexity analysis is important as we are mainly interested in finding optimal algorithms that use fewer
computer resources. Complexity theory is a field of algorithms that deals with the analysis of a solution in tenns of computational
resources and their optimization. Humans are more complex than, say, amoeba. So what does the word 'complexity' refer to here?
Complexity is the degree of difficulty associated with a problem and the algorithm. The complexity of an algorithm can be observed
to be related to its input size. For example, an algorithm for sorting an array of IOnumbers is easy, but the same algorithm becomes
difficult for I million inputs. This shows the connection between complexity and the size of the input.
Thus, complexity analysis is useful for the following two purposes:
I. To decide the efficiency of the given algorithms
2. To compare algorithms for deciding the effective solutions for a given problem
Consider the following scenario: for a problem Z, two algorithms A and B exist. Find the optimal algorithm. To solve this,
there must be some measures based on which comparisons can be made. In general, two types of measures are available for
comparing algorithms--subjective and objective. Subjective measures are factors such as ease of implementation, algorithm style,
and readability of the algorithm. However, the problem with these subjective measures is that these factors cannot be quantified.
In additi on, a subjective measure varies from person to person. Therefore, in algorithm study, comparisons _are_limited to some
objective measures. Objective measures, unlike subjective measures, can be quantified. The advantages of obJechve measures are
that they are measurable and quantifiable, and can be used for predictions. Often time and space are used as obJect1ve measures
fo r analysing algorithms.
lO ' \ ' ' "- ' ., ... , " ''·'"' , , , t >/ 11,i:_ , •I , ,,,,,, ,
l
,- ,,.,. , ,m111/, \I i i- nw nrn, tlw 111lll' tnkl'll h\' :rn nlg n11t l1111 to ex ec ute lot'. din c rc nl in ~n.: asir~ g inr 11 t<; ( i .e., dilf'c rcnl) _,
inp11i--) ln nl ~\'I 1t hm -.; tll,h . t,, ,, time frKIPt , ni c cP !l<.1dc 1c d e~l'l' llt11 ,11 l1111 c _;ind run lim e . l·,xc1.: 11ti on tim e ( ,ir com p~ ~C'._itl~-11
l"h'l' '- 11,, 1 ,k p l'tHi \'11 p rnbkm m,tni11' r s . /\dd111nnnll v. n p1o g tr1lll
111 "Y_b c comril c d m ::m y t i rn cs . T hc rclfJn.: , ti m e i n an a i' c 11 ttil ,
,',' ll h ' '\. I ,ii \\ .1, , n' k r, 11, tlw t llll ttm t' .,, ,,nh thi... .._ c hn~ nc t~11 /l' C! hy 11~s_1.'1.11 cc<1 ., /\no,t h c t c
or~1p lcx i_ty i" ~\'/ H i c e ~·"mfJfrxi,;<:1Lh1,
, , t hi' 1\ll'il:-\IIY \11(' 1)\ , , r nll' l l l l ' " ,pncl' 1L'LJl l ll'l' llH.:llh () I :111 .il g ori Ihil l. I 1.:d1111 c .il Iy, .i n ;i Ig o r Ilh m ,.., cf f 1c 1
c n1 Ir lcc,<;cr re'!( n,!·f
>ur<-t ,
.11C \I :-,',\ l ' h ,1p 1c1 ·"' f,,c\1:-L' ' 1)11 the :111:ilysi:- ,,r:i lgorit h111 s .
In alg,, nt hm :-IHdy . t1111r complc~1t y. is not men s n rcd in a bso lut e term s. For_ ex~m pl~ , one ca nn o_l sa y th e ri lgn ri thn, ta
l (, - :S l' L' ll ll 1h . lt 1:- \\l'l'll l?- AS time l'\)ltl plcxit y is olways dc t~ o tcd as a co mpl ex ity lu~ c t1 0 11 l (n) o r T(n) , w he re l (n) I<; a r}e,
tH,n o f rn pu1 :-i.1 .:- . n · nnd is not an ahsolulc value. T he va riabl es n a nd Na rc us ed inl~rc h a n gea bl y a nd a lway 'i re'lervectll:·
T'\.'f'rt'" 'n\ th c input s i 7 c nf the al gor ithm. Recollect that i~1pul s ize 1s th e num~e r_of bmary b its used_to _repres~nt the i,, 1,,
m:-t::i.n,-.:- . TI1c lo g ic here is that for larger input s th e ~lgo_n thm wo uld tak e m o t e ~1me. For exa ~pl e , so rtin g _a li s t of I f) :i:r
mcnt~ ,s cr-t ~~. but so rtin g a li st or 1 billion e leme nt s ts dtfTi c ult . Ge nera ll y, algorithms wl~ose tim e co mpl ex ity fun ction i~.·
ha ve exponential fun c t·1 ,d
r0 I~ no n11a· 1. 1-o r cx a mp 1e, say ,\ I o r Io~g ,"v. cac tl be so lved eas tl y ' but problems whose a lgo rithms 011

:-a ~ 2'. are diHicuh to soh-c.

Example 1.1 A ssum e that there a re two a lgorithm s A a ~d B for a given proble m P. !he time complexity. functi o ~
a lgorithn1s A and Bare. respecti ve ly, 3n and 2". Which algonthm s hould be selected assummg that all other cond 1t1ons refllain
th e same for both algorithm s?
So/11rio11 A ss uming tha t all condition s remain the same for both a lgorithms, the best algori~hm takes less time when the
111 Table 1.3.
inpu1 is changed to a larger va lu e. Res ults obtained employing different values of n are s hown

Table 1.3 Time complexities of algorithms A and B

Input size (n) Algorithm A T( n) = 3n Algorithm B T(n) = 2n

1 3 2 ,,
5 1-p 32

10 30 1024
2100
100 300
- -

It can be observed tha t a lgorithm A performs better as n is increased; time complexity increases linearly and gives lesser
100
\'a lues fo r larger va lu es of n. The seco nd a lgorithm instead grows exponentially, and 2 is a very large number,
Therefore, algori thm A is bette r than algorithm B.

Example 1.2 Let us assume that, for a problem P, two algorithms are possible- algorithm A and algorithm B. Let us also
2
ass ume that the time comp lex ities of algorithms A and B are, respectively, 3n and 1On instructions. Here, n is the input size of
9
the problem . Let the input size n be 10 instructions. If the computer system executes I 0 instructions per second, how much
5

time do algorithms A a nd B take?

9
Solution Here, n = I 0 5 , and the computer can execute 10 instructions 5
per second.
•
3 = 0 .0003 seconds
Therefo re . a lgorithm A (time complex ity 3n) would take xIO~O = _1_ 104 •
-
5
2 I O X (10 )2 IO I OI 0
= I 00 seconds
Algori thm B (time com pl ex ity I On ) would take = x
IO 9 109 .
ft can be o bserved that a lgorithm A would take very Jess time compared to algorithm B. Hence, it is natural that algorithm
A is th e preferred o ne.
On_e may wonder w hethe r thi s has got a ny thing to do effic ie ncy. Imagine that we are now executing algorithm A on a slower
5
machine- a machine th at exec utes5 o nly I 0 ins tructio n s. What would be the scenario in this case?
3 1
Al go rithm A wo uld take x 50 = 3 seconds
I0 .
 lntrodurtirm to Algorithms 11

\\ ·c l·,rn thnt nlgn11.· lhlll /\ 1s

Sl'C · still
· hcth.:
r compared to nlg,on·thm B tlwl l,1 . kcs, IO ~_ 1 -= IO'' , d There fo re the
- ~ secon s. . '
better al gorithm indcp cnJcnt of speed of10the mnch
impl,11:int l'l'111t ll.' be nl,ted here is that/ \ is still
ine. I lcn ce , while computer
~rel'd ,~crucial.t he t\ 1 le of n bcll1:r designed algor
ithm is still significant.

1.6.6 Implementing an Algorithm and Performin

g Empirical Analysis
Al1l' r the algorithm is designed, it is expressed
as a program and a suitable programming langu
algonthm as a code . After the program is written, age is chose n to implement the
it must be tested. Even if the algorithm is correct,
n0t giYe expt'cted results. This may be due to synta sometimes the program may
x errors in coding the algorithm in a programm
fa ult. The error due to syntax problems of a langu ing language or hard wa re
age is called a logical error. The proce ss of remo
debugg ing. If the program leads to an enor even ving logical errors is called
in the absence of syntax error s, then one has to go
correct the algorithmi c errors. back to the design stage to
Now. complexity analysis can be performed for
the developed program. The analysis that is carrie
de\'eloped is called empirical analysis . This analy d out after the program is
sis is popular for larger programs; a new area, called
where analysis is performed for larger programs exper imental algorithmics,
using a dataset, is emerging. A dataset is a huge
of an algorithm; the standard dataset that is often collection of valid input data
used for testing of algorithms is called a benchmark
of the results of a program on a benchmark datas datas et. Interpretation
et provides vital statistical information about the
This kind of analysis is called empirical analysis beha viour of the algorithm.
(also called a posteriori analysis). In addition, the
to denote the process of nmning a program on a term profiling is often used
dataset and measuring the time/space requirement
of the program empiricall y.
1.6.7 Post (or Post mortem) Analysis
A problem-solving process ends with postmortem
analysis. Any analysis should end with a valuable
the questions that are often raised in this problem-s insight. The following are
olving process:
I. Is the problem solvable?
2. Are there any limits for thi~ algorithm? Is there
any theoretical limit for the efficiency of this probl
3. ls the algorithm efficient, and are there any other em?
algorithms that are faster than the current algorithm?
Answers to these questions give a lot of insight
into the algorithms that are necessary for refining
to make them more efficient. The best possible the design of algorithms
or optimal solution that is theoretically possible
a lower bound of a given problem. The worst-cas for a given problem specifies
e estimate of resources requi red by the algorithm
Theoretically, the best solution of a problem shoul is called an upper bound.
d be closer to its lowe r bound. The difference betw
bounds should be minimal for a better solution. een the lower and upper
The difference betw een the upper and the lower
mic gap. Technically, this should be zero. However, bounds is called an algorith-
in practice, there may be vast difference between
bound. A problem-solving process tries to reduc an upper and a lower
e this difference by focusing on better planning,
on a continuous basis. desig n, and implementation

1.7 CLASS IFICATION OF ALGORITHMS

As algorithms are important for us, let us classify
them for further elaboration. No single criterion
rithm s. Figure 1.5 shows some of the criteria used exists for classifying algo-
for classification of algorithms.
1.7.1 Base d on Impleme ntation
Based on implementation , one can classify the
algorithms as follows :

I Algorithms I
I
I I I I
Classification Classification Classification Classification
based on based on based on area of based on
implementation design specialization tractability

Fig. 1.5 Classification of algorithms

 Alg/;thm An

"Tim e is 1110 11e 1·.

- Benj arnin F
ra11~lin
L
.
leamin.g Objectives t and efficie nt. An algori thm is consid ered
. . tO d •gn an algorith m that is both correc
is is very impor tant becau se it is nee efficient n o1
Too ~\~ cl Rn nl9{'nthm designer is es~ch as time and space . Algori
ter res~u r~e\;r com paring algorithms to choos
thm analys
e the optima l one for a given proble m. Analy
sis for ~;~arv pn
It A Is ~ ' I $nd use:- few compt~th thm analys is. The reade r~ erat1ve
~~ th.> <?ffi..~nc). of an
algon m!nf ~.so hapter This chapter also prese
' ul"$l,~ l r;f;J-Onthm:- 1s th e focu:s o t 1s c ·
nts the basic ideas of algori
OUld be D~
,::i, ° ' ~ in:
;.;.r.~ ,, ::+i tht11 f,, 1,0~1,ng et" ncepts by the end of th is chapter: ar
• \ ~ "' fo· :,.,mr,\>'l.11\ analys is V(
• S.~.:s l'l .:-0,;_r-J.>'l.it\ :malysis of algorithms
• r.-"'3 s "IC ~ m,-e '°'tftui>!K) rr
• R.:;,~ cl~-"~ s•1.:l il~F'•rithm behaviour c,
• ~ "$ ;:--f 35) 'l\!.'!'c'! ', ,ma~-sJS
t1
• ~"\- .. ~ ~..:'":-",." .."'- j~• '1 .:'!Sti-U ~
1:
.. ~..~ :,.._v--~~ ~ \ ~!\
05
. s.s.~-s ;:• ~ '!' n:-s 1 :n-alysis C

3.1 6..l\ SICS OF ALGOR ITHM COMPLEXITY

s of comp utation~
that deals w ith the a na lys is o f a lgo rithm s in term
.,_ ,--; ·-· -: - · .·.·-·~·:,:, .':r :i:, ,,,,. is 3 br..u.H.::h of algorithm study and space . Thus , ont
s:.:,·::· .,s :i r..:,• .m J ,;pJl'e . ..-\.n c'.(licie m algor ithm utilizes few comp ute r resou rces in term s of time
:-;:..;._,::...- ,"-,._,_ theo ry. The comp utabi lity theory deal,
.-L- ,,-::::-.1.., : u.':::' ,,i,.i-".· ri , ·e-;; o t' th
<c" ,·omplexiry theory \\·ith those of the com putab ility
theo ry is conce rned with
em. On the orher hand , th e algor ith m comp lexity
••~:.': :.-..-;., :.':;:'-..' :-::'t ,·..1~ i:-...,l! -'S l,( s,, h-:ibiliry of 3 probl 366 secon ds in machine B
::::,Y:- ::'::,·..i : :$..<~ '.'t.'1.1t. -J w th<c" .rn3l ~·sis of algor ithms . A sta teme nt such as ' a lgori thm A takes 0.
:::-,: runs slow ly in a particula:
the efficiency of an algor ithm. An a lgo rithm th at
·::: :-:.·: ·'-' ~ --:. .:..' ~~,: u :_. ,c1Juc-s cmo01 deten nine nde nt o n many facto rs such as mach ine
- · .. -- -.:- -- 3 ~ - · - ;';os·e- m .nwth
er m3chioe. Thus . the speed of an algor i thm is depe
size, and data structure<
. :-.:-.·;:- .::.::-.: :.::f '..illf:U .lfe . errici ency of comp ilers that deal with the lang uage tran s la tio n , input
~-.:.. on , style , reada bility, under•
_-..?-.:.. ~:: .:.:.:.:::,,::. :::-:- ..::~i i: ,, f an .il1writhm
depen ds on factors such as its ease of im p le m e ntati
theo ry for estim ating the tilDl
~ , ± -- ~ . .::..: ;;._-:: ; ::..:~:: . Then" i~'re. !.he cl13ll
enge is to de,·el op a gener ic comp lexity a na lys is
hin e or softw are environment
.=,.:.. ~.:. .-:;: :'.:"~ ..:..:...~ :-~ .o::. .LfL' :-:tl,...7 1 such th Jt
the analy sis is indep enden t of a parti cul a r mac
.!._.:- ~...!...' ;:._;:. .·:· :::-:- e::e-...- :::,--:> ,..·,,r:: p!exi r: ,,f 10
algor ithm is requi red for the follo \\·ing reaso n s:
by predi cting the algor ithm be hav io ur
-:: ~:::::-..::_- :.:.-:- e .:~.::--:>:-.:~ '-' r' .illy gi \ ea algor ithm
solut io ns fo r the giYen prob lem
: -: : :-.:-.: ·,:.:..::- .:. :':-.:..-::--:> " ,,:-;; :·,,~ ,·l,m p.uin g algor ithms or
mine the effici ency c·
ble fo r a giYen probl em. If the aim is to deter
-...-...--.::.=:-: :::..:..: :-;-. ,· -=-i 2 :-:~-::s. A .illd B. Me 3nila thnb
are requi red to quan tify the a nribu tes o f the al gori
::::r. ~;.-~==~ ~_:. . ~-..':-.:.-;2:--:> :.::.:.>:::.. ~ - :> n ~0 rne spn-
l.
ific meas ures
--. . ....:_,: ~ ~-".:. _.. : :.::-= =~...:..., ·2--~ :5 g1 \ CI) lll Fig. 3.
 /lo w I of Alynrit/1111 Anol_p i1 45

" re aluo nth m'i based

Oflcn . ,1 t'l not p<1<1'l th Ic lo comp,, ' r, . .
M~a~ures to,
I .. qc of irnrlcmcntallon,
Oil ~11hjcr l i VC 111c;1GllfC'I GII C 1 Wi CH . '
Algnrlttin, 8nAlysls
nlµor ith,n qfylc. itnd 11ndcr'lfiin<l~1htl it y ol algo rit hms,

i
fl ~ q11ltjcr l1 vc rnra GllrCC! di tfcr Imm r cr<ion In r cr<,on

11r from 1i1 nc lo li me. I lcncc, ohjN tiw• IIINI V!trf'I' arc

L -
Suhw,-th•;, n,Pasures-
((-> fl , NI S(' nf
,rnptpmenmtion)
Clt,jectWe meesu,., J H:q1111 cd ror pcrlnrnw11cc cva lu::it ,nn . <icncra ll y. lbcr,c
111ca~ urc~ i11cl11dc rn ca 'l urcrncntc. of qomc comrutcr re-
source,; ~uch a'l comput 111g <;peed. mcm()ry rcqutrcmcnt,.
1 disk usage. and network u'lngc. n,cd ,o,;cn r,hJcct1 ve
_j_ -

Dynamic objective
measures
--

j 1
Static objective
measures
meas ures should be qu,111tiri;ib lc. und ~hould ,il,;o have
predicti ve power and inherent 'l im pl 1cily (JbJCCt1ve
measures can furthcr be class ifi cd ns sta llc and dynam ic
(e.g .. time and space) (e.g ., program length)
objecti ve measures.
Fig. 3.1 Measures for algorithm analysis
Static ob_jective measures Static objecti ve measure'!
. . do not depend on input instances. These measures do
rwt change 1TTcspecti ve of how many instances of an algorithm are scaled (or increased). Examples are program length and
pr,1gram wilu me. Though static objecti ve measures are simple, they are not suitable for algorithm analysis.
Dynamic objective measures Dynamic objective measures are immensely popular. These measures are dependent on input
in~tances and hence are more accurate. They include run-time (or execution time), memory space, cache hit ratio, disk usage,
and network usage. Among these objective measures, computing resources such as time and space for measuring run-time is
,·ery popular.
Time complexity is more important than space complexity. This is due to the declining cost of primary and secondary
memory devices. Hence, except in embedded applications that should be implemented in limited space environments, space
complexity is not of a much concern. The implementation of a program involves two time factors- run-time and compile
time. Run-time can also be called the execution time. For algorithm analysis, only run-time is considered, as compile time
is not important. A program may be compiled or recompiled many times, and hence is machine-dependent. Thus, time in
algorithm analysis always refers to the run-time that an algorithm requires to produce expected results for legal inputs. In
addition. the running time is not expressed in units of seconds, minutes, or milliseconds, but in tenns of CPU cycles . As time
comple xity only aims to predict the algorithm behaviour when the inputs are scaled higher, the units are often immaterial
and hence would not be quoted explicitly.
Time efficiency or time complexity is a measure of how much run-time an algorithm requires for execution when the input
size is scaled. Scaling an input means increasing the value of an input. A variable Norn is usually reserved to represent the
input size of an algorithm. Therefore, time complexity is always expressed as a measure of the input size. Input size is the
length of the input of an algorithm. Why should input size serve as a basis for complexity? For example, sorting of a list of
IOnumbers can be easy. However, the same sorting algorithm becomes complex when used for a list of a million numbers.
This shows that a direct relationship exists between input size and complexity. Thus, time complexity analysis aims to predict
the beha viour of an algorithm by determining the relationship between processing time and input size as a function t(n) or T(n ).
Let us discuss the methods of computing time complexity in the subsequent sections.

3.2 INTRODUCTION TO TIME COMPLEXITY

Let us talk about measuring time complexity. To determine the run-time function t(n) or T(n), two decisions are important.
The first is one to select/identify an appropriate computational model and the second one is to find a suitable measuring unit
to characterize the algorithm complexity. As discussed earlier, the complexity of an algorithm should be independent of any
machine. In order to avoid machine dependence, a physical or real machine must not be considered for algorithm analysis.
Therefore, all algorithm analyses start with a notion of a computation model. As discussed in Chapter I, a model of compwa-
tion is an abstraction of the functioning a real-world computer. A virtual model has clear specifications of the input and the
relationship between the input of the algorithm and the expected output. In addition, the model provides ideas about the steps
or operati ons that would enable the computation of time and space complexity. We will briefly discuss one such theoretical
computing model , called a random access machine (or RAM) (refer to Box 3.1 ), in the following section. CPU cycle is the
basic measuring unit to characterize the algorithm complexity.
 , ,, , 1, \\ l\'ll\ hinr
r .....rt
~
~)"I"- I1 '"
., i
t·l '11 1lm,1dPl tl\nl!1pp1oximn1
:- ,1 ,\ , 111111., n '
' ►,' ,
11s An inslructlon has two
For oxample. ADD 8 is an Inst pa~S-Ope ration
, ~.,,,,, 'I<\\''' ·' , It "ri)lllil\f w1t11 nn lnpul t11w1co, ruct1oh wh Code
• ,,11 I \1,11 1\ i' ! l:,t
,-v ~ 1" ' ,, ,,~ . :, , , 1 .u,d 1111,rn,in r11 1, n,omoryRAM incl11d0s n nnd B Is an operand. A rando maccess rnereAoo
, , , Isan and r.
,,, , \' .I \\ \ l ' I many sue h instructions as LOA X(I ach1neis °Dora?<
~~ n~ dnlo A ,so so
of address location X), ADD X (a~~~ an accurnuia:: r,rti,,; •
I \
·t
:\' ,, .a' •"• ,, • 1~!\• l,l ' ' ~(f\ i1 1\ll 1~•• , . woll
' , 0 1

• l\ \ )f~. .,,, 1:,. .-)mi

,,. ,' ,, .._ •_,. , ·, •,,,,, ,,t ~ -,til l\~gistar 1s CAiied an
1 ' '~1101 ' at location X to the content of a he content Of Wilh 1h '">,
1 11 1
ti;~,'"~
d.,tn ,1r ,ntorn,edln le results. Each ccumu1a1 0 A) me "'·
,, 1' \"' • ' , •• . ,
I .~\'. '\ J~\' \\ ~ ,-, ,.., l :,.t\
1 • \. of an accumulator at memory location X r , STA (sto~o~1;·
" , , , _, 1 , ,,_,,_i .111 ,nt,~wr Operand values are not importa nt 1n. ), and Hait (h , eIn~ .
1 . a RAM a,1 1~ ,
'\'~'\ .~...: •:~ ., _:3,1t~, ~1111t1l.11t1d u~1ng tl RAM. Theref~re, a ~AM 1s not dependent on addressing . is a1so as , and Jh-
It • e~.
' ll! a ,
. .
''• , h t t '\ [)Clites sequentially. These, , 1nstruct1ons 1s required to execute one operation nd a surned thai v.:::
,._, l "-'' ,' ' ,::tn. ,'l\•n~t .l I t t .
one space u netr.
0
to store one value.
' '"' , " ~ ,• 1 •r '' t"l1r.nt in::tructions for reading and writing mtegers · . nt1 ia
' ,· \ 1'1' '· .. ' . t t· s
nrithmetic operations. con tro I ,ns rue ,on Th us, an aIgonthm ,s converted to a . r,.
, set of 1nstl'\J .
,, ,, 1 ~ •1 ,'t' ll\tlllN I , . k
th e given las s. For example, the algorithm ct,ons lo
, i .,r: 111rhim1 subroutine call. and return statement. staternent s iltr,,,
$, \~", ,~ ,'\''lv!t1111, 1V , -• ' . .
be translated as follows ·
..., • :: .1 q ~1r"t\lr,im i$8 S8{]l1t:Jnce of 1nstruct1ons. . , Xi ;

"ad the accumulato r with the content of location 1000d where Xis stored
.:i~ h\\' l ,.
ontent of
t
the accumulator to Y. th ath i s sore at 1ocation 2000
~:,~ :,'\\) ~dd th e c .
·e -ult at location 3000 that is were S 1s present
~ T~ 3\),1(\ Store the 1 ~
f. ~l T Ha lt
Logarithm cost model In a logarithmic co st model th
The time complexity of an algorithm is estimate? by ?ounting the
pendent on the operand. If a larger integer 1· ' e~.
number of operations. Thus. every step of an algorithm 1s tra.nslated . . s_used, the ~
determined as the logarithm of the size of nlhe er.,
to a set of statements of a RAM. Every step and every operation of a Operand rnu1t·
1Plied t.
RAM is supposed to get executed in a constant time. In this c~nte~, .
factor c (e.g., clogn). This model can easily be simulated .10
one can classify RAMs into two types: unit cost model and logarithmic world computer by scaling down the computer t·im ewttha a;,
. .
cost model. A u111t cost model 1s more robust and used more Wide!COns,,
Unit cost model In a uniform cost model, the cost for performing
because computations based on a logarithm cost model do Y. Tr
an operation is assumed to be one. In addition, the cost is not dependent
much from those based on a unit cost model. Ooic
on the operand.

d in the follow·tngtwo,
With a suitable model such as a RAM, time complexity analysis of an algorithm can be performe
I. Mathematical analysis 2. Empirical analysis
is translat d;
Marhematical analysis (or a priori analysis or theoretical analysis) is performed before the algorithm e'
Thus; mathemat ical analysis is used to estimate time complexity in terms of step count or operation count
program.
The following are the advantages of this mathematical analysis:
operating system, corr;
I. Mathematical analysis is independent of any particular machine, programming language,
·
interprete r, and case tool.
2. It is applied before the algorithm is converted to a program.
An analysis of an algorithm before the actual code is developed is immensely useful, as
it helps in detennining the effici
solution has a limit, then'
and theoretical limitations of the algorithm (refer to Table 3.1 ). If the problem is unsolvable or the
the constraints of the pror
alternate actions can be detennined either in the form of approximate solutions or by relaxing
because the anaip
Another kind of analysis is called empirical analysis. This is also called a posteriori analysis
study is called experi,r,
perfonned after the implementation of an algorithm in the form of a program. This area of
time T(n) is detennilli
a/gorithmics. In empirical analysis, a program is executed with real-time datasets and the running
the algorithm. The adiar
clocking the speed. Then numerous statistical tests are performed to predict the behaviour of
parameters. This helpspt
of empirical analysis is that it can accurately find the values of machine-dependent algorithm
run faster. Differencesti<r
measurements accurately and, if necessary, tune the parameters of the algorithm, so that it can
these two types of analyses are tabulated in Table 3.1.
Sections JJ-J.5. frn;
Mathemat ical analysis is more popular than empirical analysis and is discussed in detail in
rsive) algoriUJJ11l
analysis is discussed in Section 3.7. Let us now discuss mathematical analysis for iterative (non-recu
 Basin of AIKnrithm Analysis 47

3
Table -1 Compari son between mathematical and empirical analyses
M1lhematlc1l 1nalyala
Emplrlcal analy1l1
Mathemntic-,al analysis is done before th . . .
oonve11ed to a program. 0
algorithm 1s Empirical analysis is done after the algorithm is converted
to a code.
1 This analysis is independent of th
, machine environment e program language or
' . This analysis Is dependent on the program language or
machine environment.
This analysis is also independent of input instances.
Results of this analysis are dependent on the distribution
of inputs, and all machine dependencies are taken into
account.
F~r lengt~y alg.orithms, the analysis is difficult. Therefore
th,~ technique ,s preferable for small algorithms and is of, Length of the program is immaterial. Any program of any
\ hm1ted applicability. size can be handled. Therefore, this technique is more
I practical.
Sound mathematical knowledge is required as the analysis
I is based on mathematical concepts. Sound mathematical knowledge is not required .
I
T~is analysis i~ independent of software testing as the
pnmary focus is only on algorithms and not on program code. This analysis is more related to software testing.

3.3 ANALYSIS OF ITERATIVE ALGORITHMS

The steps involved in carrying out mathe f 1 \ · c: h · · · ·
ma 1ca ana ys1s 1or t e iterative (or non-recursive) ·
algonthm framework are as follows:
I. Measure the input size, that is, the length of the input data.
2. Measure the running time using either step count or operation count.
3. In th e case 0 ~ operat~on count, find the worst-, best-, and average-case efficiencies of the
algorithm. It is naive to think
that for all kmds o~ m~uts: the algorithm works uniformly. In some circumstances the
dependent on the d1stnbut1on of the input data as well. performa nce of an algorithm is
4. lden~ify the rat~ of gro:"th. T~s step determines the performance of an algorithm when
the input size is scaled higher.
Scaling means mcreasmg the mput size and assessing the behaviour of the algorithm.
The behaviour of an algorithm
can be determined only after observing its performance when the input data are scaled
high. Let us discuss these steps
in a detailed manner in the subsequent sections.

3.3.1 Measuring Input Size

Algorithm analysis is dependent on the size of the input. The input size (usually denoted
by nor N) is defined formally as the
number of binary bits used to represent the input data. The efficiency of an algorithm is
always expressed as a function of the
input size. For example, finding the determinant of a matrix of order 3 x 3 may be a simple
task. However, if the matrix order
becomes l 024 x l 024, the run-time of the algorithm increases, Therefore, the input size
becomes very crucial. Let us now
find the input size. The following are some of the typical algorithm inputs:

Integers Integers are typical algorithm inputs. The common practice is to use the number
of bits required to store an input.
Consider the famous problem of primality testing. The primality testing algorithm takes an
input number N and checks whether
the given number is a prime number or not. Since the input of a primality testing algorithm
is a single number, let us assume
that N = 1O. Therefore, the input size is given as logi(N) = 4 (as the binary representation
of l Ois 1010). It can be observed
that the logarithm function is used to make numbers small.
Matrices For many algorithms involving matrices , such as matrix multiplication, addition/
subtraction, matrix inverse, and
determinant, the order of the matrix can be considered for finding the input size.
Arrays For algorithms involving arrays (or sets or tuples) of many elements, the order
of the arr~y can be used as the input
size. For example , let/= (Xi, X2, .. . , X,,), then the size is given as log of n, that is, log
2 n. Here, n 1s the number of elements
present in the array.
Graphs For algorithms involving graphs, either the number of edges or the number of
vertices, or both can be used as the
input size of the graph .
 3.3.2 Measuring Running Time
l he nnr 1.1~i.. i), fl) dctc1111 111c the 1111111i11g
,·:rn be l·:111 wd 1)t1f 111, /llWI I S "avs. Soni
1i111c of an algo ri1h111 , whi ch
c orthe 111cthods that arc used
d
r-::::::,-~ l
/ Ys,s

in Fig. 3.2 and an.: also disc usse

f~,r 111c.1~111111g 11111 11111c arc shn~vn .-- --- ---
hnc fl , in the 1iillo \\' 1ng subs ec ti ons.
oac hes. One approach
•\ l~tm thm nnnlys is has two do111inanl appr Step count Operations ~ ' ,
an in his pion eerin g book titl ed Des ign and coun t 1. .
" n~ propo~cd hy Ullm sur- - -- '"lyr,
s- usin g step co unt as a mea -
.411,1 /i ·sis tJ/A l~orithms in th e 1970 Fig. 3.2 Methods of run I ar,,}
or 1111;- tim e of an algo rithm . Late r this can be used to deter- in1e rneas lJ t
ing t;nit ther rerner
given algo rithm . Ano
mine the upper and lowe r bounds of the
osed by Knu th in his popular book titled
dt,minant approac h was prop . unit for run-time
estimat,·onrs . th
r to Box 3.2) , where the measuring
ThC' Ari o(Co111p11ter Programming (refe are dete rmined, and based on that ' the b ound e bas co,
1
age case s of oper ation coun t
count. Then worst • best ' and aver s of an "'-
book , thes e two appr oach es have normally been used.
ca n be determined. In thi s of a RA alg
coun t is base d on the fact that an algo rithm is basically a set of instructions
The concept of step execute the algorithm · manualJM. therefr,
a RAM model (refer to Box 3.1) and to.
idea is to use a virtual machine such as ally and semantically meani.nYfuto esr'OJ,'
uctio ns it wou ld take . A prog ram . . step is defined as a syntactic .
number of instr . The 0 tberg I ins,,'
. ment can be considered a prog ram step
•u
ent state men t or a cond 1t10n al state
For example, an ass ignm •niec011J
as a function of step count.
ofa n algorithm T(n) can be expressed g all basic operatio P

nd meth od of dete rmin ing the run- time is based on operation count. ~sin ns enipl oyei
The seco the idea is to find an ele
ity may be a difficult task. Therefore,
algorithm for estimating time complex rations arementary (or ba
and expr ess time com plex ity in tenn s of the number of times the basic ope perf o~ d
dominant) operator ..,,e . In
. 1 . 1s . the operation . count of an aIgon.t hm.
t rme comp
exrty ing time . The .d
ysis to illustrate the behaviour of the runn
The third usef ul way is to use asym ptoti c anal
com putin g the actual time complexity. This analysis
can be co~~~ of asyni
oxim ation s rathe r than
analysis is to use appr rnect Wi~
step count or basi c operation count. ner.
ation count methods in a detailed man
Let us now di scuss the step count and oper

m!J Donald Ervin Knuth (born in 1938)

not a popular jargon till 1950s. Much of
the analysis of .
'father of
Donald E. Knuth is widely considered the notations was popularized by Knut h throu gh h. _algorithms
comp uter scien tist and IS mu, lti_·volume vr.
algorithm analysis'. He is a great titled The Art of Com puter Programm ing. He also
at the Stanf ord Unive rsity. He was t ·b · popu anzed asym·•'
professor emeritus · H. .
. immen
analys·IS IS
Wisc onsin , USA, in the year 1938 . ana IysIs. is con n utIon towards algorithm se H.
born at Milwa ukee , setting syste m, MET AFO NT-a f~t e
analysis. created TEX computer type
Knuth made great contributions to algorithm and algorithms such as Knut h-Mo m·s-P d,
ratt a~omr
algor ithms is much ancient lion langudage,
Even though the history of . · hing string s. ,
uters itself, the word 'algo rithm ' was (d iscusse in Chapter 16) useful for matc
than that o_fcomp

Step Count · . .
instr ucti ons or step s that are used b perfonTI the given
The idea is to co unt the num ber
The first step is to fi nd steps per exec
of
ution and ireq ~ uency (or number ofy( a give ) f
n algo nthm to
ofs1e~
II Imes o stat eme nts. The number · ·
le sta teme n t d t t Th .
exec ution is O for non-executab s an gene ra Y I for exec utab le
s a eme nts. 1s num ber vane s onl)
· · ct b
a functron is invoked or composite stru ures are processed for .
exampl
. e, re
t (
urn a + + c) can be considered one
_ + h ·
0 n the othe r
hand , fo r instructions such as 'n' , or both are depende
step co unt· ,·sno t I I add-- ~ n'. w ere e~ther van able 'a' or vari able the s·
input instances , the • n a rtr on ' 1f a fu nct IOn ts ·
· mvo ked , then the step cou nt depends on
the function.
Some of the. spec ific ways of meas uring • step cou nts per exec ution are as follows:
. .. . . 1,:
arati ve state men ts with no initializa tions have a statement cou nt of 0. In case 1111t1ahzat10ns are made. ·
I. ~ecl
co unt 1s 1.
n/end/end if/ eo d whI!. e/end for all have a step count of O.
2. Comments and brac kets such as begi
 //11\irs of Alwl1'ithm Analysis 49
~- I \!)1'l' S~1011C. h 1l\1.' ' l ~1" J) ,
1
· · • 1.:m111t 111' 1
-1 \:--~1g111111·111 Sl,lll'lH1.' tll ltlll ' I
. l h)tl111,n -•11 . II
h.11 c .1 :-tep c,111111 11 r 1. l, '"" · n.:t11111 ~1n1c 111c111s. nnd other slntc,ncnl !-l such as break/co ntinue/go lo a

rt\'l.jllt'lh .' \ 1sthcn11111hrr11r1 · .. .

ltlll:- (ltl ll l s tru r t' \ .
nnd ~ll'l'' rc1 n1.'C11lH,11 . I r t 11~ ;1 11
1 . · ic 11 is c., cc ut cd. The totfl l co1 1111 can he obtained by multiplying the frequency
. . p yt ll S c,wi.,
1 th
1.: p, o) ems. to Ill out l 1c compl cx 1ly uncti on o qornc o r
1() ~O lll ' . l I 1· d I . f' . ,·
.1If,,ntI1111~ . J • · thc ba~1
.c

Ji:umpk.\.1 1..' ow ·ct I ·

~, 1.' r t ll' tollowi11g algo rithm segment :
Algorithm simple (A, B, C)

4 = B + 1

fnd
C= A+ 2
D= A+ B

Find the step count of this algoritllt

11
segment.
_J
Solution It can be observed that the st f .
1
is. a computer system need not execute tiep count o t 1e instructions I , 2, an d 6 1·s O, as ti1ese are not executa bl e statements, that
· lese statements. The executable statements are 3, 4, and 5. This is shown in Table 3.2.

Table 3·2 Step counts of a simple algorithm segment

Step number Program
Steps per execution Frequency Total
1
Algorithm simple(A, B, C) 0 - -
I2 Begin
0 - -
3 A = B+ 1 1 1 1
4 C=A+2 1 1 1
5 D = A+B 1 1 1
.1
6 End
I 0 - - ,,
Total
I 3
I'<
-·

It can be observed that the total is calculated by multiplying the number of steps per execution by frequency. Therefore,
T(n) = 3. This means that the algorithm computes a fixed number of computations irrespective of the algorithm input size.
Therefore, the algorithm is a constant time algorithm. What is the implication of this algorithm analysis? Constant-time algo-
rithms are easier to compute, as they are independent of the input size. These algorithms are tractable or solvable. Therefore,
the complex ity of the preceding algorithm segment is simple and, therefore, the algorithm is easily computable.

Example 3.2 Consider the fo llowing algorithm segment that computes f I and estimate the run-time using step count.
1= !

Algorithm sum()

Begin
sum= 0.0
for i = 1 ton do
sum = sum+ 1
End fo r
Return sum
End
 •. ,1,lc stut c111c11t s, 1111d hence steps per cxcc 111 ion .
I x ,,re 1Hlll· l'Xlll 111 · . . 1or lh
ln:-tll1l·111m~ 1• .. . • [l lH ' '
1 (1
s,1/uri,m I l'tion•il itcrnlion is required lor lhc control lo c C~c ~l
, t I , f , , l ·y p ( II 4 I ns [Ill 11(( I ' ., , , , ,, IIn1 c l <ll ,
,'\'r1' . :-.lll ll'llK'llt .. l!l~ !1 I\ qmt ( . I , ' . ·x nc;11tcd '11' times. 1 his IS shown Ill ruhl t: 11 1u1 ()I ~'r1
. l ,·
~tnti:nwnt ~ I~ " 11h111 I lC nr oop. 1c1 l I l'I ·
, · ·ltll'C t H.:y ,Il l,; C, i.; .. ' [L \
• •1~ 1, '
Table 3.3 Step count analysis •1

Step count Frequency

Step no. Algorithm segment
0 0
Algorithm sum()

I2 I Begin 0 0

!3 ' sum = 0.0

n+1 n+ 1
14 I For I a 110 ndo
sum = sum+ 1 n n
5
I 0 0
\ End for 0
I6
7 Return sum

8 End 0 0 0

Total 2n + 3

Therefore, the step count of these instructions is n. The total count is obtained by multiplying the steps per e .
~
. 1unct10n. of thts
. aIgont. hm segment. Xecution1
frequency. It can be observed that T(n) = 2n + 3 is the time complexity

As evident from Examples 3.1 and 3.2, time complexity is not a single number but a function. More impo~
polynomials. It can be observed that th1s. 1s. a po Iynom1a. I wt'th an mpu
. t size
. n an d can be so Ive d east·1 y, as pol Y,tne
.
algorithms are easily solvable. Ynorn1a1

Advantages and disadvantages of step count Evaluation of time complexity using step count is easy How
. . · ever c
the major disadvantages of this method 1s that step count 1s not dependent on operands. In other words, the size of l~e
operand is not significant. For example, a = a + 10 and a = a + I0,000,000,000 have the same step count.
Operation Count
Operation count is another way of performing algorithm analysis. The idea is to count the number of operationsir
of steps for algorithm analysis. Operations can be divided into two categories: elementary (or basic) and non-elem,
(non-basic) operations.
Elementary (or basic) operations are primitive operations and are often implemented directly with less effort. The follr
are some of the commonly used basic operations:
I. Assignment operations
2. Comparison operations
3. Arithmetic operations
4. Logical operations

Non-elementary (or non-basic) operations are not atomic in nature and involve many elementary operations; e\J
incl ude sorting, and finding the maximum or minimum of an array.
Co~nting Lh_e number of elementary or basic operations is helpful in measuring the run-time of an algorithm. An1
operation on bits, characters, nodes, or integers can be a basic operation for most of the algorithms. Thus, the stepsr(,
for performing an operation count are as follows:

I. Count_the number of basic operations of a program and express it as a formula.

2. S1mpl1 fy the formula.
3. Represent time complexity as a functio n of operation count.
 /Jol'irr nf Alr,orilhm Anolyvis 51

Findin~ oprrnlion rount ·

· g are important
The follow 111 . . . · · h
algPnthtn. prmc1ples to find the operations count for various ~tructures m t e

Sl'QU<'m'l':

Table 3.4 Operation count of a Sequence S

Structure Operation Count

%% Sequence S
Begin
p
Q

End

Here, The p and Qare statements in an al orith

and so on. g m. Those statements could be any statements such as function call, return,
Ts is the worst-case running time of th . ·
running time of statement Q (refer to Ta:l:ei.~~~ce, Tp is th e worst-case running time of statement P, and TQis the worst-case
It can be observed that the worst-case ru . . .
addition principle. nnmg time of th e sequence is the sum of statements. This principle is called the
Selection: Let us consider the following co nd't•
1 10na 1sequence:

Table 3.5 Operation count of Selection s

Structure .Operation Count

if (C) then
StatementP
else T5 = max{Tp + T0}
Statement Q
End if

Here, C is the condition. P and Q are the statements. It can be observed that the worst-case running time of the selection
structure is the maximum of the worst-case running time of its statements (refer to Table 3.5).

Table 3.6 Operation count of Repetiotion S

Structure
, c.;..,.,..., Ope~ation Count

for i = j to k do '

while ( C) do
T5 = Tpx n
p

repeat P
until C
'

Here, Tp is the worst case running time of operation P and n is the worst case iterations involved in looping. It can be
observed that it is the multiplication of n and Tp. This is called multiplication principle (refer to Table 3.6).
Thus, it can be observed that algorithm analysis is reduced to counting of steps or operations (refer to Box 3.3).
 ; .,,, ,/l\1 1 ,,f 1/i:1)//(/11111
I l, ,,, , ,,,,

HtfE us-s-- -,P

Ce~d··-F-ri-ed_r_ic_h_G_a_ e of_M
-,-ln_c_ - ati_c_,- -- - - - - - - - -- - - -- - -S~
_ at_h_em
5

th8
➔
1 "2 + 3 • • • + 200 - ~
Johann Fnednch Gauss is considered .
grdoAI·
ftenofreferre
d one to 200 + 199 + 198 + . . ~ 1 s
°
I est mathematicians of all ~,m.es an 1777 In -------
as the 'prince of mathemattcs . He was born In 201 +201 +201 + · · · +201 2S
Bru nswick, Germany. He is credited with carrying out
st In the sequence 2S, the number 201 is a
mathematical work that influenced many fields of udy.
He was a genius since his childhood. When Gauss was a 10-ye~r-old Therefore, s
= 200 x 20 1/2 and the sum is 80 ~ 8 aririg
school student his mathematics teacher Mr Buttner asked him to leads to a formula n(n+1 )/2. The book Dis ·. ?O. l"h· ~Or,
th . Th qu,s,,.1 ta1
compute the s~m of natural numbers from 1 to 100. He produced e (In vestigations m Number , , eory) authored by G %J4 ~ ~•,
result in a flash of a second, surprising his teacher. The formula for important role in the number theory. Gauss is aus8 Pr,,Iqrr,,
. k d. an all t· ii,,..
computing the sum of numbers is as follows: ematlcian, and h,s wor s are use m very d' • 'rtie , . i
. . d ivers Qr~,
astronomy, acoustics, optics, geo esy, magnetism e areasil-,,
,oo n(n+1 ) tics, and calculus. The bell-shaped curve (for 81 •61eC1ri . i.,_
1 + 2 + 3 + --- + 100 =I i= - - . How did he compute that? The · d' 'b 1· d Gaussian eliminanda. rd distrCij,/
l=O 2 hyper-geometric ,stn u ,on, an i'.
Gauss technique that is applied to a simple illustrative example of very useful for the study of algorithms. He died ~t,o~ rtlet~~-
counting 1 to 200 = 1 + 2 + ... + 200 is described as follows . Write the Gottingen in 1855, at the age of 77.
sequence (say S), reverse it, and add it to get 2$, in the following manner:
.
in his ho '>'.;
~.

Example 3.3 Consider the fo llowing algorithm segment and perform complex ity analysis using operati
on count·
Algorithm swap(a, b) ·

Begin
temp = a
a = b
b = temp
End

Solu~ion Table 3.7 .illustrates all the operations that are perfo rmed as part of an algorith m and is fi -
run-tune of the algonthm. . nally expressed,

Table 3.7 Count of all operations of a simple algorithm segment

- ,,,.,c.;.c.-c
Operations
Step no. Algorithm statement accounted for Operation cost Repetitions Total cost
1 Algorithm Swap (a, b) 0 0 0
I••
2 Begin - 0 0 0 Ii
3 temp = a Assignment c, 1 I
c,
4 a= b Assignment
I1
C2
5 b = temp Assignment
I~
C3 1 C3
6 End
I- I I
--
I;
~ -

As evident from Table 3.7 steps I ' 2' and 6 are aII non-executable t t
~
or t he other statements are as' fo llows: ' s a ements and hence the cost is zero. Operation er.

T(n) = c,+c2+c,0
This is a constant-time algorithm The d' .
machine-dependent. · prece mg relation shows that the exact cost estimation and the con5t1JJ~·
 f/11.11r·v nlA /w1rilh111 ;1 110/y.~is 53

l\ 111si1kr tlw· ti.ill 1)\\' 111

!_.t p1 .ogra m scg111c11t :
{or ~ - 1 t0 n do
II - A '\ I..
End fo r

Perfonn l'l,mpk,ity• anal"s is of ti , t · t·

· ., , · operati·
1e ,, gont un segment usmg on count.
Solutio n As discussed earlier •:1 \1 ti , , ·
, ' 1e operallons can be counted as shown in Table 3.8.

Table 3.8 Operation count of a simple algorithm segment

~
.·.c.

Step no, Elementary operation Operation

Algorithm statement accounted for cost Repetitions Total cost
1
I Algo,ithm Sample () - 0 0 0 !!

I2 Begin - 0 0 0
3 I for k = 1 to n do Assigning, testing, and C1 n+1 (n + 1)
'

X C1
increment
4 A=Ax k Perform multiplication C2 n n X Ci ,;
5 End for - -
6 End - - - 1,,
- - -~-- .. - - - -~~-- -"'- --= -
Simply, the total cost reduces to

t(n) = (n + I) x e 1 + n x e2 =(e + e )n + e ::::: en

1 2 1
Therefore, the t(n) of this algorithm segment is approximately
en, where e is the machine-depe ndent cost and n is the
input size.

Analysis as Domin ant Operations

Counting of all the operations of an entire algorithm may be a difficu
lt task. It would be much simpler if the count of only the
dominant operat ion is taken into account. The following examp
le illustrates this concep t.

Example 3.5 Consider the fo llowing segment:

for i = 1 ton do
for j = 1 ton do
A= B x C
End for
End for

What is the operation count if only multiplication is taken into accoun

t?
Solution In the preceding example, if multiplication is the domin
ant operat ion and there are two loops for execution, then
it can be observed that multiplication is done n x n times as the
operati on is perform ed inside two loops, both rangin g from
I to 11 .
fl 11 II

:. count =L 2,l=L n=n 2

i= I j= I i= I

'
Therefore, it can be infe rred that the run-tim ' 2
e 1s 11 .
Many rules of summ ation are often required for algorithm analys
is (refer to Box 3.4).
<, /1, ,,, ,, .,,,,/ 111, ,11 11 1 P/ 1/i:, 1111'11111

llfi1J Counting
Many times . algorithm analysis is reduced to counling of steps or Some of the additional useful rule
operat,ons s are a
II $ fo11()
The following are some of the common summations that are ~ ~ -
k, k = 1 + 2 + 3 + .. . + n == n(n + 1, ·
encountered in algorithm analysis: k= 1 ~
n
n- 1
L.1 = n-1
I k2 = 12 + 22 + 32 + · • . + n2 _ n(n + ,
1
,= 0 k= 1 - ~ ( 211 ~
n 6"" , 1)
n- 1 L k3 = 13 + 23 + 33 + ... + n3- n2(n + 1 .
I c=
k=O
en k=1 -~
4
More details are provided in Appendix A.
2

Example 3.6 Let us assume that the analysis of an algorithm yields t(n) as follows:
II
t(n) = L 6i(i + I )
i= I
What is the estimate of the total number of operations?
Solution The aforementioned summation is equi valent (refer to Box 3.3) to the fo llowing relation :
11 ../!-,
1(n) = I 6i2 + 2...,6i
i= l i= I

=6 x n (n + I )(2n + I) t-
6 x n (n + I)
6 2
= n(n + l )(2n + I ) + 3n (n + I )
= 2n 3 + 6n 2 + 4n

Therefore, the time complexity function t(n) of the given algorithm is 2n 3 + 6n 2 + 4n . The
· · Box 3 .5 . reasons of al or· h
are given 10 g it rn an·'

j:rlff fi.1 Reasons for Algorithm·Analysis

On the basis of the preceding numerical problems, it can be concluded
Example 3.7 Let there be a limit of maximum 5 hours for pertor,;
that the complexity of an algorithm can be expressed as a function
t(n), where n is the input size. It can be used to predict the efficiency a task. Let there be two algorithms , A and B, having the v
of an algorithm. Algorithms that have time complexity as polynomials complexities TA= n2 and T8 = 2". How many inputs can be proce;,
(e.g., 2n + 3. n2) are called polynomial algorithms. Algorithms that have by these two algorithms in seconds and which algorithm is eflior
functions such as 2" or n! as time complexity are called exponential Solution It can be observed that algorithm A has a polynomia. ,
algorithms. Exponential algorithms are difficult to solve within a reason- algorithm B has an exponential ~n).
able amount of time. Polynomial algorithms have been proved to be The limit of the computer is 5 hours, which is equal to 12'
easily solvable, owing to the following two reasons: seconds. As the time complexity of algorithm A is rf, one can 1'
1. All machines are inherently polynomial , that is, only the constants the following equations:
vary from machine to machine.
2. Operations of polynomials are closed under addition and n2 = 18,000 ⇒ n = ✓ 18 , 000 "' 134
composition . That is, a polynomial algorithm A followed by another Therefore, algorithm A can process 134 ins · tances in 5 t;cu~
algorithm B. together forms a polynomial algorithm. Similarly, two contrast, for algorithm B, n can be calculated as fo llows:
polynomial algorithms calling themselves are polynomial algorithms
as well. 2" = 18,000 ⇒ n "' 20
Differences between polynomial and exponential algorithms are . nierefore c"
This clearly shows that T8 can process only 20 inputs. rnore inr,'.
illustrated through the following numerical example: can conclude that algorithm A is better as it can process

I
 r lJ 'rPJ!" ?irf i 4ft

/Ja 1/r i of Alwwlthm A11aly1i1 55

3.4 BEST·, WORST ·, ANO AVERAGE -CASE COMPLEXITY

1, ,, dl1'1'Knl h' ,1,.,unll' th.11 thl' ,,r. , . . • , 11 . •~ 01 nclirncY • the cflk icncy of an
· \ 1l 1l Ill~ nl :, Iµ,1n th11, ~ dl'pcnds solely 011 the 111p11t '1/.C
. .
,1\~,,:11hm ,krcnd, ,m the d1st11h1111n11 of input dnw ns \\'di. I he \\W~ t-. hc ~t-, nnd average-
case clliw:ncy of algo rithm ~ ct1n
J,c ;,111n .11l',l h ,1'11!--tdl'tllll! dil1i.·t\'11t 1· , , ,t J t 1· ·t
· ~ 111 \Ill (\ l l ~ln 111tu111~.
worst-case Complexity and Upper Bound
1-hl' .,, ,,1,1 -,·a~,,_ \.' l1 m11k:--.,t, i, :-i 1,.~""
~,-~1·11 11· t'
· • • ' s 1c ann 1ys1·s nssumtng
• the . .fhc
worst scenario. worst-case comp Iexi·tY~v( ,·i) 1·5 a complex-
1t,· hm,1 11 ,n ,,t th,- '' orst-rn,c inpt1t 1· •I · I I I · •
·_ ' · •
or\\ He 1 t 1c a gonthm takes max11num tune and causes a compu ter to ru n slower· The
~1-,n1hmnc,,J~to 11ertonn1\, , 111 . . ,·
• ~' t_ _ ,1.: -,x imum num ber of-steps or operation . s to process .
the input • accomp 1· ,1· Lh task The
for
'' ,,~h-.1~,- l' l'm pkx.lty _01 nn algorithm gives us an upper bound on the algorithm . The upper bound of 1s,1mg c · · .
an algorithm is crucial ,
as it measures the ma:xnnum computational effort required lo solve a given problem.
Best-case Complexity and Lower Bound
The 1'e 5t-case anal~·sis is given as the minimum computation time of the algorithm for all the
instances of the domain . In real-time,
\1~ 51 cases a_
re rare 111 _real-\\'orld problems and rarely reflect the efficiency of an algorithm . It represent
s the ideal or lower bound
ol an algon th m. TIHS means that the algorithm requires a minimum amount of effort.
The lower bound is a useful measure
in a\goril hm stu dy and is applied to the problem , not the algorithm. If a problem has
k possible solutions , the best algorithm
gi\·es the lo\\'er bound considering all k possible solutions. Often it is difficult to compute
the lower bound of an algorithm .
Average-case Complexity
The a\'erage-case analysis assumes that the input is random and provides a prediction
about the running time of an algorithm
for a random input. The average-case complexity (A(n)) is n·either best nor worst. It indicates
the average performance of an
algori thm.

Example 3.8 Find the best, worst, and average case complexity of the linear search.
Solution Consider a simple problem of linear search for a list of
numbers given in Table 3.9. Table 3.9 Linear search
Formall y stated, a linear search problem is given an array of num- Index 1 2 3 4 5 "' 100
bers and a target key ; the problem is about checking the presence or
Elements 23 34 12 8 9 ... 100
absence of the target key. The worst-case complexity of linear search
occurs when the item is either present as the last item or not in the
list. For example, let us consider a scenario of searching for the number 170. To decide
whether this is the last element of an
array or to infer that it is not present in the array, n comparisons are required. Therefor
e, the worst-case complexity of this
algorithm can be given as T(n) = n.
Toe best case oflinear search occurs when the item is present as the first element of
the list. Say we are searching for an
element ' 1', which happens to be the first element. Therefore,

T(n) =n
The average-case complexity for a linear search problem can be calculated as follows
: The item can be present anywhere
in the list. Thus, the probability of the presence of the item in the given array is equally
likely [p = : } Hence, the item can
be present anywhere in the array. Therefore, the number of comparisons required is as
follows:

1 I I
T(n) = 1 . - + 2 · -+ 3 · - + · · · + n · -I = -(1
I
+ 2 + 3 + · · · + n)
n n n n n
_l. n (n + 1)_ B..±1_ "" ..!!_
-n 2 - 2 2
Thus, the average-case complexity of this algorithm is also of the order of its input size
n.
 . J
l.').Hft.p\tt~ 1·111 IIW lw~1, ".1,r·t nml :1, crn11c
s ·· ' 0
case rn111plcxi1y of bubble sort.
S1tfuthm l 1'1 \\~ .,~~umc \he array a~ ~hown in Tabk 3. 10. . Table 3_ 10
. .l , •s when the lisl is already 111 the soned order as
1he bc~t case l,\ m111 ' ' l'. so 11 t, Index
,r 12. 2.1. J4} . D1ws it help') No. The algorithm for bubble sort ts. presented Ill. Chapter 7
Elements
· ·
\,1 th is ho\,k. Bubble sort still · ~ · parisons So the complex ity of the
n:qmres com · .
2
. . , ' d
r1 1g,,n 11 1m 1s 11 , ennte
asd O( 2))
11 . But tlie good thing is si nce the array ts already sorted,
~

no S\\'apping is required. So swap cost is 0.

.
The worst case of bubble sort is when the may is in reverse order as {34, 23, 12, 8}.
Still the bubble Sort al o.
. ~ . s· h . .
to compare the aloorithm s Bubble sort still requires compansons. mce t e array 15 m reverse order g r11n~1
e · 2 ' rnany
need to be done and it is 11 ( 11- \) in number. So, swapping is more compared to the
best case. Swa~f
\Vhat about the average ~ase? For doing average case, one needs to consider not only
the input but also th .
A pemrntation is the rearrangement of the elements where the original elements
are preserved. It is also called" e dist~01,
and rearrangement of the array elements 1.s such that rearrange ment preserve the one-to-o
. 1• ne correspondence ofrand°ill 0'!·
ments 1tse I. An array of n elements has 11! ordenngs . the atr .
. a,,
So the array {23 , 34, \ 2, 8} will have 4! orderings. The average case is the average
of all types of cases. Bubb[ ··
requires 11 (n-\) comparisons. But the bad part in this is since the array is in reverse eso
2 order, many swappings n d n
ee to~ .
an d 1·t ·1s n(n--1).m number v
4 . ·

3.5 RATE OF GROWTH

The primary focus of the rate of growth is to fi nd the behaviour of an algorithm .
Here, small changes are not si .
How do two algorithms differ if their run-times di ffer by only a few seconds or minutes?
For example , for two a~nific:'
with run-times of I000 and 1005 seconds, a minor di fference of 5 seconds can be
ignored. In contrast, if the co:nQ:
of one algorithm is significa ntly larger than that of another, it is a matter of concern. 1
The point here is to decid/ e:
is the better algorithm based on how the algorithm will behave when the input size
larger and larger). Thus, the rate of growth of an algorithm is the rate at which its
N is scaled higher (i.e., N be:~~:
. running time increases as a fu ~
of mput n. ¾
·
Thus, the rate of growth approach can summarized as follows:
I. Measure the complex ity of an algorithm t(n) for larger values of n.
2. Compare it with the collection of functions that have the same growth rate, so that
the algorithm can be classified,
ranked.

3.5.1 Measuring Larger Inputs

Rate of growth is helpful in understanding the behaviour of the algorithm s For understan
ding this concept, let us consid,
situation where the time complex ity of the algorithm s increases as the input size increases
through the following examplt

Example 3.10 Consider three algorithm s A, B, and C. Their respective run-time complex
ity is given as follows: r1=·
T8 = 7 log 10 n, and Tc = n2
Compare the rates of growth when the input is scaled from 11 = J00 to n = 10,000.
Solution Initially, the number of instances is JOO. Later it is increased (or scaled)
ton = 10,000. For the first algorilhrr.
whose complexity is given as 7n, the rate of growth is as fo llows:

TA( l0,000) 7 x 10,000 JOO

TA(IOO) 7 x 100
 Boiicv 0( Alxorithm tfnalym 57

Simihrl~ · thr rnt c of gro,, th ti.-ir lllher alt::ori thms cnn br obtained ns fol lows:

Tn( I0,000) 7 x log 10 I0,000

Ti(I 00) 2
1 7 x log 10 100
Tc( I0,000) 10,000 2
Tc( I00) \00 X 100 10,000
th
Ii 1.· an be nb~m ·_ed at algorithm A grows by 100 when the input is scaled up from I00 to I0,000. The second algorithm
15 1
l1. g,anibmic. ,~·hich _grows JUS t by a factor of 2. The rate of growth of the third algorithm is around 10,000. Therefore,
I.he se-:ond algonthm 1s better.

L-:t us consider four algorithms with the following time complexities:

Ti(n ) = n, Ti(n) = log2 n, TJ(n) =n2, Tin)= 2n

Table 3.11 Analysis of rates of growth
We then try to identify the rate of growth of these algorithms. An analysis
Input.size n lo9in rr of the growth rates of some sample inputs and the algorithm growth rate in
2"
0
Table 3.11 . A sample's linear versus exponential growth is shown in Fig. 3.3 .
2 Here, n ranges from 1 to 10 only, as 2n. It can become very large for
10 10 1 3.32 100 1024 a larger value of n. Exponential functions grow tremendously, making
100 100 6.64 10 4
::: 1030
computing more difficult as n grows larger. Some of the popular algorithm
I classes are shown in Table 3.12.
1000 1000 I 9.96 106 ::: 10300 The rate of growth helps compare two or more algorithms. The following
example illustrates the comparison of algorithms.

Time complexity plot

500 - f(n) = n
g(n) = logi(n)
h(n) = n2
400 - k(n ) = 2"

~
·x(l)
t0
(.)
300 -
(l)
E
~
200 -

100 -

-· - -·
0-

I I I I I I I I
2 3 4 5 6 7 8 9
Values of n

Fig. 3.3 Analysis of rate of growth

Example 3.11 Let A and B be two algorithms with the following complexity functions : l.4 - n2, ta - 40n + 1200.
Wh ich algorithm is better?
Solution The starting point of this problem, is to find an instance of n where l.4 =ta.This instance can be obtained as fo llows:

n2 = 40n + 1200
 :;,;ji}F.
~1,c-" ,m,I 4,,,,/, 111 ,1/ ~lg,1111lm1,

Table 3.12 Algorithm classes

Name used for algorithm

Function name an1lyals Remarks
C
Constant algorithm These algorithms are Independent of the input.
I
I Log log N \ Log log function Logarithmic algorithms are preferred, as their growu, is al
Log N Logarithmic ways law
These are very optimal algorithms. · ·
I Log2N
I Log-squared These are optimal algorithms.
N
Linear algorithm Linear algorithms are preferred, e.g., summing of an array.
I NlogN
\ N-Log-N Many popular algorithms such as merge sort have this type f
N2 o growth.
Quadratic Sorting algorith~s are preferred, e.g., bubble sort, selection sort.
Cubic Matrix multiplication is preferred.
Polynomial Polynomial algorithms of lesser order k are preferred.
Exponential Here a is a constant, and intractable algorithms are exponential.
I N\
Factorial These algorithms are intractable.

This is equivalent to n2 - 40n + 1200 = 0

The roots of the equation are 60 and -20. We are interested only
in positive integers. It can be observed that h
both algorit. hms are equal. This is illustrated in Fig. 3.4. w enn,
For n > 60, algorithm A can be seen to grow at a faster rate than algorit
hm B. Therefore, it can be concluded that .
A and B are both suitable when n = 60 and algorithm A is more
favourable than algorithm B when the input r a1gon:.
l to 59. For other values of n > 60, algorithm Bis better than algorit
hm A. However, for other values of n (>60) alanges1
.
is far better than algorithm A. , , gonii,

Time complexity plot

~n) = n*n
g(n) = 40n + 1200
4000

~ 3000
·xQ)
C.
E
8 2000
Q)
E
~

1000

0 10 20 30 40 50 60 70
Values of n
Fig. 3.4 Plot of functions
 /111 </I In/ f /~()// //r/11 fl llOfl'l'II ~9

\ n,,1ha 1'll h.'1'mc ,,r r.lli.'

' \\( ,~1\) \\ 11' 1~ tl h' l\\111, .
1 11 ,,111.1( t,1bk 11nJ 111t rnc tab\c pni bl c 111
. ~ . 11
( ~Cl: >OX
' ()
•' · ' ·

1ml] Ttactabl~ vs Intractable problems

T:-idBble Pf\.".b~.~ \N solvable problems) generally have polynom1al-
l\~ CO.iW~~~ ~~h th1S is not always right. as an algorith First square = 1 grain (2°)
m Second square = 2 grains (2 1 )
"'Ith, (.'!()11'j.'le -;;il\ n . IS worse th an that with complexity 2fl. this kind
of f\oS.Sc 'ic..3ron IS ,nm,~nsely useful infom1ally. Algorithms that have Third square = 4 gra ins (2 2)
°'
f:li."lo\'1);.Y.llal· 0ga.,lhmie'-type complexity are easy to solve.
Intractable Continuing in this way, the number of grains in the 64th square
°'~ · °':the
~ eXt"Xlrtent·al atgonthms.
other ha nd • are known as non-detem1inistic polynomial would be i 3 = 9.223372 x 10 18 . This is a very big number, and it can
be noted that the number of grains required is many hundred times
Tr tl\Jstrate an exponential algorithm, let us consider the famous the yearly production of grains worldwide. It can be observed that with
~ boa"CI 8 ?'1 grain problem . An Arab mathematician lbn Kallikan
every unit rise in the square of the chess board, the number of grains
a,..s;,,'(ed a question in the 12th century-if a grain is placed
in the first grows exponentially. This kind of algorithm is called an exponential
square ~ 8 chess board. two in the second square , four in the
third algorithm . Even if a computer takes only a few milliseconds to process
squrue, eight In the ~urth square , and so on. how many grains would
be an instruction, an exponential algorithm program would run for many
required to fiH an entire chess board this way? The answer is as follows:
hours, months , or even years.

3.6 ASYMPTOTIC ANALYSIS

Asymp roric analysis is the theory of approximation. Consider

for a moment the Gauss summation, that is, ~n n(n; 1). This
is an exact fommla. which has a ·closed fom1 ' solution. In real-w
orld situations, finding an exact fonnula is often not possible .
..\symptotic analys is is a very old discipline in mathematics, and
asymptotics is basically an approximation tool. Asymptotic
is a Greek word for approximation. An ·asymptote of a curve is
a line that closely approximates a curve but does not touch the
curve at any point of time. It can be very effective for algorithm
analysis where finding the exact time complexity is difficult
by the process of counting. Although finding time complexity
is easier for small algorithm segments, it is difficult for larger
programs, as enumerating all possible inputs and finding an exact
count are very difficult. In addition, time complexity can
be accurate only when many parameters that are dependent on
the machine are include d. However, these additional machine-
dependent parameters affect the generic nature of the algorithm.
In this context only, asymptotic analysis is important. A brief
history of asymp totic analysis is given in Box 3.7.

lmlJ Brief history of asymptotic notations

Asymptotic notations were used by Paul Bachmann (1837-1920) Vinogradov notation is ~n) « g(n). If t(n) » g(n), this is equivalent
in to
the numbe r theory. Later, big-Oh (0) or big-omicron and small-oh g(n) « ~n). Similarly, the little-oh notation can be written as follows:
(o)
or small-omicron notations were introduced by Edmund Landau if ~n) = o(g(n)), then the equivalent notation is<« or <.
in
the early 1900s. Edmund Landau took this notation from Bachma Hartmanis and Stearns used these asymptotic notations for rep-
nn's
Treatise on Number Theory . Therefore, the big oh notation is resenting the complexity of algorithms initially, and these notation
often s
called a Landau symbol. were popularized by Donald E. Knuth for specifying the complexity
The Russian mathematician I.M. Vinogradov used alternative symbols of
algorithms in his series of books on algorithms.
for the big-Oh notation, which are as follows: If ~n) = O(g(n), then
the

The limit theory is helpful in specify ing this type of algorithm

~eha_vio~. . .
For examp le, consid er the time complexity of an algorithm, which
1s given by the following relation :
3
+4
t(n)11=--
n
When 11 becomes large r, this becomes as fo llows:
4
~aj= -+-4 ,i2 + n
3 1
11 n +0
=-- =-- =n 2
11 l l
Thus. it can be observed that n1 is the asymptotic behaviour of
1(11) when n -+ oo. In general, a limit of two complexity
fu.nctions can be ,, ritten as fo llows.
 o n.-11>-"1 .,,,., 4,,,, I', ,, ,,f 1/,:,
. ,1 ,1/1111 1
"
. .
. , ~it ivc co nstnn
. , then both complexity
1 c, Iuncti.ons are of
. -~ii\' 1iinL11 011s is ,t 0
P· , r·
d •r it is 00 1, ( 11 ) grows aster.. the
. l 1 rnl t'I f\\ i, nrn1p 1c . sail)
l IIH' tt 11· 11 ·l1111i1i sll.l1(11)grows, foster .
an I . , • I h' I d
k. i11to '1ccount only t 1e ,g,cs t cgrec ofap eo
t ih. 'i,m· ra te ic
f!T'''\ :i l . • I
. , . ,ates time cn111p c:-..1·1y by ta 111g h h.
olyn ri
t ,11. •111alys
. . L
t , re depe nden . om
t on l e mac me in Whi ch h •a1, l ·
:\ s~111p l l • . • . _ · 1s·Japprn x111. .
. c "cncrnllv ignored, as the const an s u .
l •mi, :ind m11lttphl:1n s ar "' . I rror is very snia 11 .
. This foci is demonstrated 111 Exampl e 3. 12. t e alg\l~\l1i,\1
l • • . rror? Yes, but t ,c e t~.
Doi.'~ o1111~s 1011 lead to an c '1,

. . two algorithms:
Let there be the tollow 1ng
Example 3.1 2 J
. t. 1e + 11
1. r\lgorithtn A with runn,_ng ,_n f - 11-
, A.12.orithm B with runnmg time 111 -
"= ,,2
-. . - k for 11 == t 00. How long w ill it take for n
. . takes one second to compute a tas
Assume that each ope1ation
ti t algorithm can be compute d by retaming ont
. :::: IOoo~
. Each operarion takes one secon d. Time for the ,rs 2 . . d T.
SoI 1111011 . I 112 + n only n is retame . ,me computatio Y th
n t e dor
degree of the polynomial. Therefore, 111 ti,e given polynomia
. . , or al
is as follows: go~
2
1000 + lO00::::: 99.1
TimeA = 1 x 1002+ 100

. ti
Similarly, time computatio 'thm B is as follows:
n or a1gon
10002 - 100
Time 8 = I X 100 2-
. . .fti ' --....
It can be observed that no s1gmficant d1 erence ex1·sts between TimeA and Time 8 (here, the d1ffere nce is 100 _ 991
Thus , in asymptotic analysis, constants can be ignor .~
ed.
3.6.1 Asymptotic Notations
• · I .
Asym ptotic notations help to c asst'fy aIgon·thms and specify the upper and lower bounds of algorithms.

o- Notation (Big-oh Notation)

The 0 -notation (Big-ob Notation) can be used in
the following instanc~s for
expressing the upper bound or the worst-case
complexity of a? algonthm.
It is used to express/(n) as 'is never more than
' or 'at most' , given another
comp lexity function g(n).
The formal definition of the 0-notation is given e x g(n)
:
Let t and g be two functions that map a set of natur Q)
al numbers to a set of E
positive real numbers, that is, t: N ➔ R ~ 0. Let O(g) ~
be the set of all functions
with a similar rate of growth. The relation t(n)
= O(g(n)) holds true if there
exist two positive constants c and n such that t(n):::;
0 c x g(n).
The function t(n) is said to be in O(g(n). This is
denoted as t(n) E O(g(n))
or simply as t(n) = O(g(n)). This implies that
t(n) neve r takes more than
approximately g(n) operations; that is, t(n) is in
the order of g(n) or simply a
function with a grow th rate that is:::; to that of g(n).
This implies that t(n) grows Input size n
at a slowe r rate th an a constant time g(n) for all
the values of a larger input of
size 'n' . This is show n in Fig. 3.5. Fig. 3.5 Big-Oh Notation

Example 3.13 Let t(n) = 3n 3 for an algorithm . Prove

that t(n) of the algorithm is in O(n 3 ).
· G. h
o
S I utwn 3
1ven t e statemen t, g(n) = 11 . The defi111t1on of
· · . . 1
in O(g(n)), wher e g(n) is n3, one has to show that 3
the O-notat1on 1s that t(n) ~ c x g(n). In order to prove tha vr~ a!,
3
3n '.S cn holds good for a posit ive numb er c and
of n. It can easily be seen that this condition holds for sufficie11 tlYlarge
when c ~ 3. Therefore , t(n) is in O(n 3) .
 /lm/1'1' 11/ Algnr/1/1111 An11/ym 61

·111 ➔ 1, n ➔ 1 1-or nn :1l g.unth111.

1
t umplr.\.14 l cl r(11) 1 . I.et g(11) :: 1
11 . Prove that r(n) ol• thi•s aIgori·l h·in 1·s 1·11 O( n 1) ·
SoluriN1 171c ddiniti1)11 llf thr hi, OI . .
. . . I:,· 1 notat,nn ,s 1ha1 t(n) $ c x g(n). Therefore, one has to show that 111 1 + 2nJ I 1 ,,.., r.n 1
l1t,l,i:- gl'l'd hlr :1 po~,, I\ C' n11111lwr (' 'lllCI r) . ' 11· '. . I
• t I su 1c1c11t y 1::irgc vn lucs of 11 .
T(n) = 31/ + 21/ + ~
< ~1r'+1 ,r'+ 111 '(
- • - • as growth offunctions 11 2 $ 3 and 3 $ 11 1)
5 811·1

It cJn be obser,ed that c = 3 + 2 + 3 _ ( . . , . ,,

• • · 8 one can approximat
Q:00 dt or any ,·a1ues of c > 8 Ass · - e 211 2 and 3 to 211J and 311 3 respectively ). rl11 s cond1t1on holds
- - · ummg c = 8, one can say that this algorithm is of the order of 0(n 3) .
3
Example 3.15 Let r(n) = 2r + 13 logi,t .. .
?n2 for an algorithm A. Prove that t(n) of algorithm A is 0(n).
Solution It can be observed that 1 - · I
. og x < x IS a ways true. Therefore, one can argue that 13 log x < I3x and as I3x $ 13.x-J
a1ways, one can rewnte t(n) as follows: 2
-
15113
t(11 ) 5 -
711 2 "' 211 for all n > 1 and c = 2
:. 1(11) = 0(n)

Example 3.16 What is the complexity of log I + log 2 + ... + log n?

Solution By using the property,

log x +log y = log xy

One can write the
log 1 + log 2 + ... + log n = log (I x 2 x ... x n)
= log (n!)
5 log (n")
$ 11 log n

:. one can conclude that the complexity is 0(n log n).

Example 3.17 Prove that 210 is 0(1) (Refer to section 3.6.2 for limits).
Solution For
lim f(n) = c
g(n)
n---,~

i10
lim- = limi 0 = i 0
n ➔ oo } n ➔ oo

As 210 is a constant, one can conclude that it is 0(1 ).

Example 3.18 Consider an algorithm that is assumed to run in time O(n 2) and that takes only five seconds to compute results
fo r an instance of size 30. How long will the algorithm take to compute the results if the instance size is increased to 50?
Solution Recollect that O(n 2) implies that t(n) $ c x g(n), that is, t(n) 5 c x n2. Here, c is a constant that depends
on the
machine. As mentioned in the problem, the algorithm takes five seconds to compute 30 instances. Therefore, one can calculate
the values of c as follows:
cn2 steps = 5 seconds
c(30)2 = 900c steps executed in 5 seconds.
5-
. c=-
.. 900
 I · ' of 41\!0111/1111 1
f.2 Jlr,ign mi, 1411•1 ' ' '· • •
sily be calcul ated. If the algorithrn i
. . , II other instances can ca
0nl'.c the' n\uc s of c arc dec1'dd lltn
c., e lor,1 be calculated as iO
"II 'Is· nstan1: .
. rogram can ov . ~ 1~-
10 50. then the tnnc 1akcn by t1 ,e P ,\
c(S0)2 = 250 0c

--_ _ill9_= \3.88 seconds

5
. · equation, one gets 2soo x900
Substituting the value of c 11111115
. . 13 88 seconds to execu te 50 instances.
The calculallon shows that the aIgon·1hm requires .

n- notation (Big-Omega Notation)

The lower bound of an algonthm . . . by the Q-notat1.on (Big-omega notation).
IS given . . . as follows:
The fo nnal definition of tl~e big-omega
notation 1~~e:umbers to a set of posi
Let i and g be two functions that map a tive
set of na f ll th e functions that hav
·
real numbers , that 1s, t: N ~ R?.O. L~t Q(g) be the set o a os e Ill
hold s ood if ther . E
a similar rate of growth. The relation e exist two F
t(n) = Q(g(n)) g
positive constants c and n0 such that t(n)
~ c x g(n). .
.
Thu s, the function t(n) 1s. sa1'd to be m· Q(g(n) which can be represented .as
1(11) E Q(g(n)) or c x g(n) simply ' . . · plies that
as t(n) = Q(g(n)). This notaffit10~ imtl
t(n) orows at a faster rate than a cons large n
•
tant ttme ( ) for a su 1c1en Y
The Q. notation , which is the lower boun g n d. F' 6· Input size n
d of an algorithm, is illuS trate 111 tg. 3
The Q-notation can be defined in term ··
s of limits too. Fig. 3.6 11-Notation
Example 3.19 Let t(n) = n4 + 3n3+ 2n
+ l. Prove that t(n) of an algorithm is Q(n 3).
Solution The big-omega notation is ~
defined as t(n) ~ c x g(n). ln order to prov th
to show that n4 + 3n3 + 2n + l ~ c x n3 e at t(n)_is Q(g(n)), where g(n) is ni,or
holds good for a positive n~m_ber c a3nd
be seen that for c ~ ln ~ 0, this condition for sufficiently large values of n. It can
holds good. Therefore, t 1s m Q(n ). 1

Example 3.20 Let t(n) =6n2 + 8 and

g(n) =n, show that 6n 2 + 8 E Q(n).
Solution For Q-notation, one has to
prove that j(n) ~ c x g(n)
⇒ 6n 2 +8~ cx g(n) .
For n ~ 0 and c ~ 0, this condition hold
s good ; therefore, one can show that 6n 2
+ 8 E Q(n ).
0 - notation (Big-theta Notation)
Both the upper and the lower bou
nd can be illustrated by this nota
The average-case complexity is also give tion.
n by the 0 notation .The formal definitio
of 0-n otation is given as follows . n ex g,(n)
Q)
Let I and g be two functions that map E
a set of natural numbers to a set of
positive real numbers. If the relationship i=
c1 · g(n) $ f(n) $ c · g(n ) holds goo
for all n ~ n0 and there exists constant 2 d
s c1 and c2, then t(n) can be denoted
t(n) = 0 (g(n)). as
This is equi valent to saying that l(n)
grows at the same rate as a constant time
g(n) for all suffi ciently large values of Input size n
n. The 0 notation is shown in Fig. 3.7.
Fig. 3.7 0-Notation
Example 3.21 Let us consider that t(n) 4
= n + 3n 3 + Sn + 1. Prove that t(n)
of an algorithm is in 0(n4 ).
Solution The 0 notation is defined
as c1 x g(n) $ t(n) $ c x g(n).
In order to prove that t(n) is in 0 (n4), 2
first one has to show that
c1 x $ n4 + 3n 3+Sn+ l
$ n4 + 3n 4 + Sn 4 + n4 as (3n 3
~ 3n4, Sn~ 5n4, I < n4)
$ \On 4
 Basics of AlgorithmAnalysis 63
Ilcan be observed that this condition holds good for
c.l0. this condition holds good
Neu proethat +3n'+ 5n +|scsth!

and c;l0, the abovc condition holds good.

Inother words, the algorithm Therefore, t is in On').
complexity in ').
is
Example 3.22 Prove that 9n+4 is O(n).
Solution
The notation is defined as c X
g(n)sI(n) Sc; Xgn).
In order to prove hat (n) is in O(n), first one has to show that
CXns 9n + 4
c, Xns9n+ 4n
c, Xnsl3n (as 4 < 4n always)
It can be seen that when c, s 13,this
condition holds good.
Next, prove that
9n +4S Cn
=9n + 4n S Czn
= 13nS cn
This condition holds good when c, > 13. Therefore one can conclude that 9n + 4 is
G(n).
Example 3.23 Prove that 8n'+ 2n + 1is O(n).
Solution
The notation is defined as c, Xg(n) sI(n) Sc, Xgn).
In order to prove that r(n) is in O(n), first one has to show that
cn' s8n+2n +n
(as 2n <2n' and 1<n)
slln
c,Sl1, this condition holds good.
Next, prove that &n' + 2n + 1sc, x g(n) (as 2n <2n' and 1<n)
8r + 2n+ n s cn
=8r + 2n' +n'scon
= 11ns Czn
When c,>11, this condition holds good. Therefore, one can conclude that 8n' + 2n +lis O(n).

Example 3.24 Suppose that an algorithm takes eight seconds to run on an input size n= 12. Estimate the instances that can
be processed in 56 seconds. Assume that the algorithm complexity is O(n).
Solution Assume that the time complexity is O(n), then cn 8seconds. Here, the instance nis given as 12. Therefore,
12c = 8; hence, c = 8/12 = 2/3.
The problem is to determine the value of nthat can be processed in 56 seconds. This implies that c Xn= 56. The value of
c has already been determined as 2/3. Therefore, 2/3 Xn = 56. This implies that n = 56 x 3/2 = 84.
Hence, the maximum input that is possible is 84.
 o-nototion (Little-oh Notation) Table 3.13 Differences between
The httleoh notion is used very rarely. 0-notation can be used
instead of the (-notation, as the o-notation represents a loose
O-notatlon O- nota
0-notation
ion
Tight bound
ound The o-notationcan be detined as follows.
letrandgewotunetions that map aset of natural numbers
0-\o0senotatiOofnnon-thelpsh re
For some values of c, the following
0 a sct ofpositive real numbers, that is, t: N’R. Let olg) be For all
Condilionvalues
condition should be satisfied
the set ofall functions with a similar rate of growth. The relation
r)= Og)) holds good, if for all c given , such that tn) s cg(n)
tn) <cxgln)
nn)cxn). situations where tight bounds In
The ditferences betwveen O-notation and o-notation are given
in the following Table 3.13.
need to be used, the O-notation is
prefered. s-notitautaiotionneednsis ploWhrefeeberreeAuBt.
hounds
w-notation (Little-omega Notation)
The formal definition of the little-omega notation is as follows:
Let r and g be two functions that map a set of natural numbers to a set of positive real numbers.
be the set of all functions with asimilar rate of growth. The relation (n) = o(g(n) holds, if
there exist
that is, t: N-
cand n, such that r(n) >cXgn). two
The differences between l-notation and w-notation are similar to the
differences between positve o
0-notation is aasymptoticallyloose bound andthe condition should be satisfied for all values ofc.
are very useful when loose bounds are needed. The O-o-nnototataiotinon andand o-
on
Tilde Notation
This notation is useful when the functions (n) and g(n) grow at
the same rate. For example, if f)
growth, then one can write that r(n) ~gln). and gn) have tie
The six popular asymptotic notations are summarized in Table 3.14.
Table 3.14 Asymptotic notations
Name of the How it is
S. no. notation What it means represented Mathematically
equivalent to
1 O-notation Growth of fp) sGrowth of gin) tn)= Olgln)
2: Q-notation Growth of fn) 2Growth of g(n) tn) =2(gn)
3 O-notation Growth of fp) =Growth of gln) tn) = (g(n) - (Roughly equal to)
4 O-notation Growth of fp) << Growth of gln) t(n) = olgn)
5 0-notation Growth of fn) >> Growth of gln) tn) =o(fn)
6 Growth of fn) is same as g(n) t(n) =gln)

3.6.2 Limits and Asymptotic Notations

Table 3.15 The relationships beve
Asymptotic notations can be obtained using limits as well, The theory of limits is the and notations
basis of calculus. Limit is a notion that shows
whether a function diverges or converges. Description Notation Used
Limits show the behaviour of afunction. Will an 1,1,1
infinite series -+-+-+.. ever c is positive or zero O-notation
converge? The answer can be found using the limit theory that 2 4 8
would converge to unity. As the time indicates that the series cis positive or o Dnotation
the limit theory can be used to complexity of an algorithm is also a function, c is positive -notation
study the behaviour of the algorithm.
-Notation
lim I(n) c 0S zero
gn) -notaton
Based on the value of the value of c. the C IS oo

in the following Table 3.15. asymptotic notations are used as shown c is 1

~notation
 Basics ofAlgorithm Analysis 65

O-nototion
The detinion of the 0-n0tationcan also be piven in
ferms of limits as follows:
Ii the lmt lm
*holds good, then ro) =Oe) This is called the big-Oh ratio theorem. As n ’, the
ratio will

Example 3.25 Let ro) =9n'. Prove that this

algorithm is of the order of Or).
Solution Using carlier
this condition holds good.examples, one can showy that 9n scn² holds good for all
This implies that O(n) is correct. values of cgreater than 9. Assuming =7;
The same conclusion can be
obtained using limits too:
lim
9n
=9 and is positive.
n
Therefore, On) is correct.
Example 3.26 Prove that 2"*2) = 0(2").
Solution
Here r(n)=2"* and g(n) =2
lim 1(n) =cwhere 0 <c<oo
g(n)
2" x4
lim -= lim = lim4=4 (a positive number)
n’oo

.2+2) =0(2")

Q-notation
If the limit lim: r(n) #0 holds good, then ((n) = 2(g(n). This is
g(n) also called g(n) the 2 ratio theorem.

Example 3.27 Let us consider that r(n) = 7n +4. Prove that this is of the order of 2(n).
Solution Here t(n) = 7n +4 and g(n) =n.
Itcan be proved using the omega ratio theorem as follows:
4
7+
7n+4
lim
n’o
= lim
1 n-1+0
Therefore, one can conclude that t(n) = ln)

Example 3.28 Prove that 2" + n N(21)

Solution
As per S2-theorem,
lim =c, 0<c<oo
g(n)
2" +n' n n'
lim = lim+ = lim1+ 7=,a positive number.
n-’ 2" n’o

As the limit gives a constant, one can conclude that

(n) = 2(g(n) =2(2")
 sit d 4nahsis of 4lro iths

O-nototion
definition is as follow...
The notation can be also defined in tems of limits. The formal
fn)
lf the limit ln =C, cis positive, then I(n)= O(gn))

o-notation
The o-notation can also be expressed in terms of limits as follows:

The function r(n)= o(gn)) if lim 0. which implies that t(n) = o(g(n)).
g(n)

Example 3.29 Let (n) = 7n + 6. Show that r(n) is in o(n').

7n +6
Solution As we know, fun) = o(n) as lim =0
n
Therefore, one can say that 7n + 6 o(n).

Example 3.30 Prove that n' o(n')

Solution
As per o-notation limit
n'
lim 0
n’ n

.. one can conclude that n + o(n')

Example 3.31 Prove that n² o(n)

Solution
As per o-notation, it has to satisfy the equation
lim =0
n’oo
g(n)
n²
lim=l#0, therefore one can conclude that n'# o(n)

w-notation

The relation (n) = wgn)) holds good if and

only if lim n’oo
g(n)
The formal definition of ~ in terms of limits is as follows:
lim:f(n) =1
n’o
g(n)
Example 3.32 Find the notation for the function t(n) =
50n +6 is in gn) =n
Solution
lim 50n' +6 6
= lim50n +
.. 1(n) = n
0(gn)) = o(n') n’o
n²
 Basics of Alyorithm Analysis 67

Example 3.33 Prove that 4 = o(4")

Solution
T(n)
lim:
n gn)

4n 4" .4" .4"

lim = lim = lim 4" = o
4

:. 4" = o(4")

Example 3.34 Prove that n! o(2")

Solution

Acordingto Sterling's Approximation, n!= V2rn"

n!
So, lim lim
2

=V2n lim Vn (2e xim 1+))

= V2r xo X1
=00

n! = o(2")

L'Hospital rule
This rule can be used if the functions n) and g(n) have derivatives.

lim = lim
gn) g'(n)
If lim f(n) =oand lim g(n) =oo, thatis, both converge to zero, this rule can be used.
n-o n’0

Thus, the ratio of two complexity functions is the same as that of its derivatives.

Example 3.35 Prove that In ne O() using L'Hospital rule.

Solution Consider the following limit to find the asymptotic notation: lim Inn
n'
Here, t(n) = In nand g(n)=n.
The L'Hospital rule can be used now. Recollect that lim:fn) = lim f'n)
no g(n) n’o g(n)
Applying this rule results in the following:

1
lim = lim -=0
n’oo
2n 2n
.:. Inne O(n')
 extractingnew
notationsand information
3.6.3 AsymptoticRules
usetultor
asymptotic
manipulating d1scussedinthefollowing
are
subsections.
about he beh
Asnow nesare mportantrules
of he other
tunctons Some Notations
PropertiesofAsymptoric
properties of
O-notation:
giventwo ploynomials, the
Essentiol

Onls
ae
the
some ofthe

onlythat
In
degree of
other
Ihe tollo ng dominatingsummand matters. thepolynomial
words,the

observed
matters.
that allterms
other than the
highestpolynoma i
I. fasterand
degreegrows On'+n'+64) = Ou').Itcan
Forevample,
be
the polynomial matters.
dcgre ate,
onlythe largestdegree of
Proof follows:
generalizetheresultas
m. Then one canshow that (n) = O(n")
Onecan degreeis
be r(n) = ) an' whose
polynomial
Letthe
givenas follows:
Theproofis +laln+lao
lam-n"+...
n) s la,ln" + for n21
lamn+...+ la,ln"+la n
sla,l n" +

=cXn"= On")

2. Law of Composition it is meant that O(O(tn) = 0((n).

By law ofcomposition,
3. Multiplicative constants significant.
omitted, as constant factors are not
Multiplicative constants can be
Forexample, 0(3r') =0(r'). where k+ 0.
Ingeneral, Ok- gln) = Ogn),
omitted
4. Smaller terms can be
For example,
n+n=Or) and
n+2"= 0(2") example, On loe .
polylogarithm (log n)) grows slower than any polynomial (n") for a, b > 0. For
Also,
ofAddition
5. Summation Rule-Law
The law of addition states the following:
t(n) +gn)= 0(max (1n), g(n)})
I(n) +g(n) =2(max {1(n), gn)})
t(n) + g(n)=O(max {1n), g(n)})
6. Multiplication Rule-Law of Multiplication
Let i(n) =Og,(n)) and t,n) =0g,(n), then t,(n) x t,(n) = 0g,(n) x g,n).
7. Symmnetry Rule
1(n) =(g(n)) iff g(n)=(In)
8. Transpose Symmetry Rule
I(n) = 0g(n) iff g(n) =2fn)) and (n) = o(g(n) iff g(n) = o(n)
 Basics ofAlgorithm Analysis 69

9, Reflexivity Rule
For any general complexity function (), the reflexive property is given as follows:
r(n)= Ogn))
T(n)= S2(g))
I(n)= O(gn)
10. Transitivity Rule
The transitiveproperty is defined as follows: if )=
and gn) are complexity functions of two algorithms. This O(øn) and gz) = 0(h), then (n) = 0(h(n)). Here I(n), h(n).
property holds good for other notations also.
Some of the applications of these rules are
illustrated through the following numerical examples:
Example 3.36 Prove that 16 lg n! = O(n lg n)
Solution First Ig n! can be solved as follows:
lg n! = lg n + lg (n 1) + g(n-2)
+... + lg 1
< lg n + lg n + lg n +... + lg n
=n lg n
16 lg n! = 0(1) · O(n lg n) 16 = 0(1)and
Og n!)= n lg n.
= 0(1 · n lg n) (using the law of
=0(n lg n) multiplication)
Example 3.37 Prove that (n) =8n'+7n+9n+8log n is O(n).
Solutin One can use additive rule as follows:

O(1(n)) = max(n, n°, n, lg n) using law of addition

=n'
= On')

Example 3.38 Let (n) = (3n' + 2n + 2)lgn. What is the final complexity?
Solution (n)= ((3n' + 2n' + 2))x lg n
= On) x Og n) = 0(n' lg n)

3.6.4 Asymptotic Complexity Classes Table 3.16 Asymptotic classes

A group of algorithms that share the same time complexity are called asymptotic
Asymptotic class Remarks
complexity classes. Two algorithms are said to be in the same class if the rate of
growth of these algorithms is similar. Based on this, the asymptotic classes that O(1) Constant algorithms
are possible have been constructed, which are shown in Table 3.16. O(log n) Logarithmic algorithms
An algorithm that grows faster than any power of n is called a superpolynomial
O(log n) Polylogarithmic algorithms
algorithm, and a subexponential algorithm is a function that grows slower than
an exponential function. Algorithm A that grows slower than algorithm B can O(n) Linear algorithms
be written as A < B. This can also be written as AcB using set notation. Then Or) Quadratic algorithms
the following order is prevalent:
On) Cubic algorithms
O(1)cOlogn) c On) c On logn)c On) cOn)cOt) co2)con!) O(n) Polynomial algorithms
So far, only time complexity has been discussed. However, for an efficient o(K") Exponential algorithms
algorithm, space usage should be minimal. Box 3.8 discusses space
On!) Factorial algorithms
complexity.
 und Analysis of Algorithms

Box 3.8 Space Complexity Analysis

Space complexity refers the analysis of space that is required for Example 3.39 Consider the
an algorithm. The space here refers to the following two components: the space complexity?
Begin
fol owing program
Fixed Component End
return n;
Ts Is defined as portions of memory that are independent of the
Solution The space complexity is
Inputoutput of a program. The fixed component refers to the following: and processed. zero as no
1. Instruction space
2. Space required for simple variables Example 3.40 Consider the
3. Space required for storing constants the space complexity? fol owing program
4. Space required for a set of variables or aggregates Begin
i = 0;
segnen
Variable Part S = 0;
S = S + i
This is defined as portions of the program instances that are dependent return s;
on the program input/output. Examples include referenced variables End
and stack space. Therefore, the space complexity S(n) refers to fixed Solution Here, two variables are
stored
Component +variable component. S(n) 2 2. and
proces ed.Tr:
3.7 EMPIRICAL ANALYSIS AND ALGORITHM VISUALIZATION
Efficiency analysis of alarger program using mathematical analysis is difficult. Algorithm
be analysed using empirical analysis or a posteriori analysis. Empirical analysis is useful
such as estimating the time foralarger algorithm and for performing comparison betweentwofor
efficiency
of such
out prog f
carrying
or more various
analysis ignores machine-dependent parameters and thus is independent of the machine.
gates the machine-dependent constants to tune the algorithm parameters that
result in
algorithms.analAysiss
However, empirical
analysis is useful for verifying the results of the a priorianalysis. For example, if r(n)optimal solutions. In
is the mathematical anal. addition,e
An) is the empirical result, then the ratio,I"indicates the
An) closeness of the these two analyses. Ideally, this
constant for varying input sizes. The following are the steps of empirical ratio shoul:
analysis:
1. Determine the experimental purpose and decide on
2. Generate a sample input dataset. efficiency metric.
3. Analyse the results of an algorithm using
statistical tests.
3.7.1 Empirical Analysis
The aim of empirical analysis is to run
on the counts of basic multiple algorithms on the same set of data and
operations, memory determine the efficient algornit
After the selection of an operation, a references, comparisons, or any other operations.
counter can be used as
Acount of the number of
basis operations provides a basis for part of the algorithm before and after the basic C;
Another alternative is to find the run-time of an empirical analysis.
let us assume that we have algorithm. Most
written a function called 'magic box'. In of the programming languages support tns.
of instruction. The Pvthon. there is a timeit module can assis
following code illustrates the method of
timing in Python (The details are sharedthat
in the lab manue
>>> import timeit
>>> statement =
a - 5
b 5
power a** b

Tine taken for

executing"+ statement + "\n is ", t ime
it.timeit(stmt = )