COMPLEXITY
ANALYSIS
Revised 2021 er
poror ? ee"
eliicienk
x rn wean Sa See
as di A
unly w) Sun 13) loo P
5
ohh" bso wwe)
eet 60
+: ot Lot
pate aS
<8 dsleg Fo rae . ndikion — \youk pw Al
\ wo F 90 15 oxobs Ce o 9 RY, Si ve?
Nye
‘LEARNING OUTCOM
ah WY cath salle
a“
{Carry out simple asymptotic analysis of al
(Explain the use of big’, omega, and theta notation to describe the efficiency of an algorithm
(Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on
time and space complexity of algorithms
Determine the time and space complexity of simple algorithms
Sa ag BO \iner Sears — doa ood
we we Sis owes &
Pa ®, yer edt opt &) — bodlean “Search Cay c)
COU EY & bee Cicer inet: 148
SCOPES arenes
A Eo 3M Ge
<-” Efficiency goal
af
<3? The concept of algorithm seats»
<2” The concept of asymptotic complexity —
%
ules for using big-O
| Pig(O
Comparing various growth functions
: -catlow.to determine complexity of code structures
cng © 8
ON ye os
We INTRODUCTION
What is an algorithm?
ideas behind computer programs
(Specified set of simple instructions to be followed to solve a problem.
Fixed: stays the same no matter
{Which type of hardware it is running on
{Which programming language used to implement it
(Must specifies:
sb ie Set of input >.
| “The desired properties of the output | IMPORTANT PROPERTIES OF
ALGORITHMS
An algorithm must be
(Correct -~ a
{Always produce the desired output for legal instances of the problem 4 t
(Efficient ~ bu wer yale 5 pate de me
{Measured in terms of time or space ~ . 3 § Ash SE
“Tims tends to be more important CE Soe e °
The runhing time analysis allows us to improve algorithms xs HOW TO EXPRESS AN
ALGORITHM?
We need a way to express a sequence of steps
— Natural language (NL) is an obvious choice, but not a good choice. Why?
ONLs are notoriously ambiguous (y (unclear)
lage (PL is is another choice, but again not a good
choice. Why?
Algorithm should be PL independent
< “We ‘need some balance.
We need PL independence SYN
\+ We need clarity ye a
Pseudo-code provides the right balance
Retwrad Language + presronner\
XS
4 WHAT IS PSEUDO-CODE?
Pseudo-code is a short hand way of describing a computer program.
Rather than using the specific syntax of a computer language, more general
wording is used.
It is a mixture of NL and PL expressions, in a systematic way.
Using pseudo-code, it is easier for a non-programmer to understand the
general workings of the program. EXPRESSING ALGORITHMS
An algorithm may be expressed in several ways: SS
‘An algorithm may be expressed in several ways:
Natural
+ verbose ond ombiguout
language -
+ a shorthand for specifying algorithms; leaves out
the implementation details; focus on the essence of
the olgorithm
Peeudo-code ~
poserdys Kjs08 20W
High-level
programming < + requires expressing low-level details hot are not
languages necessory for a high-level understanding PSEUDO-CODE: GENERAL
GUIDELINES
Use PLs construct that are consistent with modem high level languages,
e.g. C++, Java, ...
Use appropriate comments for clarity.
Be simple and precise. ALGORITHM DESIGN:
PRACTICE
Example 1: Determining even/odd number
— Anumber divisible by 2 is considered an even number, while a number
which is not divisible by 2 is considered an odd number. Write pseudo-code
to display first N odd/even numbers.
ln A Vor 4 &
/
f Vibun Zo (any 7 yout nunt| che
Tow - Jo?
© tea
mans ENEM EVEN/ ODD NUMBERS
Input range
for num+0; num<=range; numenum+1
do
if num $ 2 = 0 then ,
print num is even
else
print num is odd
endif _
endfor Pseudocode cannot be compiled or run like a regular program
Example.
ANOTHER got ay
EXAMPLE ay rey SE
Output: The maximum element in A
currentMax = AO]
for is] ton-1 do
ifcurrentMax < Afi] then
curentMax +A[i]
return current Max ok Lalor! sd DY at Ded! SIPS 5!
vOSUF : ‘sh Wr ao? Jase fea OEE wet Sg
wx 07% D> °
° Cc
aero. CSD ay Ke
IMPORTA | ‘4c ocany of an algorithm ie usualy expressed in
N T terms of CPU time
The analysis of algorithms involves categorizing an
P RO P E RT algorithm in terms of efficiency
(An everyday example: washing dishes
| E S Oo F (Suppose washing a dish takes 30 seconds and
drying a dish takes an additional 30 seconds
A L G Oo R | T (Therefore, n dishes require n minutes to wash and
an AO ae
HM vas
Ron SN wd ol ue a OY
; ee POS 30 rose all
ei y Wor C sore apt ie og ANALYSIS OF ALGORITHMS
Why analyze algorithms?
{The same problem can be solved with different algorithms which differ in efficiency.
We analyze the algorithms to
Evaluate algorithm performance
Compare different algorithms
We focus on analyzing :
(Running time
(Memory usage, 9 oc
jorst-case jand typical case
5 oot
ww
yg we
compares algorithms wor game
ee
w# Analysis of algorith
fbr DO) w
(we en” Bn 2S = 4 ANALYSIS OF ALGORITHMS-
CONT.
If each line takes constant time the whole algorithm will take constant
time, right?
Wrong!! es DMD els ore
The number of steps performed of an algorithm varies based on the
size of instance, called fablem or input size—\. wer
——————
The efficiency of an algorithm is always stated as a function of the
problem size -
We generally use the variable N to represent the problem size (=
St
Wor 5 TAX _
Ag KR we KRE \ n
PROBLEM SIZE 0!
For every algorithm we want to analyze, we need to define the size of
the problem —
[The dishwashing problem has a size n — number of dishes to be washed/dried
(For a search algorithm, the size of the problem is the size of the search pool
For a sorting algorithm, the size of the program is the number of elements to be sorted
/e generally use the variable n to represent the problem size
(Typically, the size of the input (n) is the main consideration
\inew Search —s ing ay
Dinard) Sear —> problem Sake ® of SP 7 oy8 , eimom Stic“ 2iee snow —sayean Sven ang se ng
P*
It is not useful to measure how fast the algorithm runs as this “lepends
on which computer, OS, programming language, compiler, and kind of
inputs are used in testing . fi
Bs Szehl © Phi io sb tg
Instead,
{we count the number ofbasici@perations the algorithm performs.
{JA basic operation is an operation which takeSTalconstantlamountontime to execute.
{we calculate how this number depends on the size of the input.
(The efficiency of an algorithm is the number of basic operations it performs. This number is
a function of the input size n. \
z
LOD op yr S s Arithmetic operations: *, /, %, +, -
. 2
Spe br Assignment statements of simple data types. —
er be? 2 D7 | — Reading of primitive types 25°" ~
Ne
AR ee Writing of a primitive type J.
‘E XA M P L E Simple conditional tests: if (x < 12)... pb ae
OF BASIC __ etotcavote ne oxctton ime ote mats
Oo P E RATI not be constant) S
A method's return statement
We consider an operation such as ++, += , and *= as
consisting of two basic operations.
Note: To simplify complexity analysis we will not
consider memory access (fetch or store) operations. Faten pes
ahr 3
eee
sowie FUNCTIONS
Bl cotta ) Gyse) Ge een QUA
ie
We must algo’decide what we are trying to efficiently optimize
>. time complexity — CPU time t
Espace complexity — memory soo]
The rates of growth are expressed as functions, which are generally in terms
of the number of inputs n
A growth function shows the relationship between the size of the problem (n)
and the value we hope to optimize (time).
This function represents the time complexity or space comple of the
algorithm. ; ced |
hve 9) gi Pe
#\ ante lA gun cs Pa ALGORITHM COMPLEXITY
Worst Case Complexity: — feces
The function defined by the maximum number of steps taken on any instance of
size n
Best Case Complexity:
{The function defined by the minimum number of steps taken on any instance of
sizen
Average Case Complexity:
[The function defined by the average number of steps taken on any instance of size
" Fae \ooud no Erk
ALGORITHM COMPLEXITY“ ~~
CONT. ey
We are usually interested in determining the -
largest number of operations that might re oz oe” »
performed for a given problem size.
Best case depends on the input Sx
Worst Case
Complexity
Or d average case
vo
pokey .
yuk ONY
gk >
vo Avo ae ayv
7 a Wd V8 or DY OU
Average case is difficult to compute
So, we usually focus on worst case analysis
{Easier to compute
=f 4, WUsually cose tothe actual running time -
sok ALGORITHM COMPLEXITY-
CONT.
Example: Linear Search Complexity
(Best Case: Item found at the beginning:
‘One comparison
{Worst Case: Item found at the end: n
comparisons
(Average Case: Item may be found at index
0,or1, or2,...orn-1
(Average number of comparisons is: (1 + 2
+... #n)/n =(n41)/2
Worst and Average complexities of common
sorting algorithms:
Method Wrst Case | Average Case
Sélection sort \ ne n
Insertion sort) | n? n?
Merge sot 7”) nlogn nioga
Quick sont” ne nlogn
J :
PK soe 8
~
8 e" ALGORITHM COMPLEXITY-
CONT. ot J ge ob poh *
Sonn
Different instances of input result coo
in different worst-case complexities
Thus, it is useful to bound the
worst-case complexities of a given
algorithm
Strategy:
Try to find upper and lower bounds of the
worst-case function
iat kha | RUN-TIME ANALY Siw. algorithms, which solve
suger
Res inte 720
PD Be ipleatior 1 oe,
(7 Sho
Vas Dt os
yeh , 4
ip OP NOW
Ail > Speed
the same problem, we check their
behaviors when they run on the
same instances of input
An algorithm outperforms another
if, for the same instance of input, it
consumes less amount of resources!
" Le., grows slower than the other one
pe be dS
‘Naniber oF pa ems
Probie se ae
Dy st
‘pesd De aeoky | Be pre
a
ot a. | oP" She
9S nena s) oe, es
ao ae ae we
ed gl CK Juego
pent, S 4 Y ok enh oF
\
ile ope BOA vert ye BEL
ebro 5 SAchaala yee pelo
WY
B gAPaers®
VK DARN 6Gr
| ae Pye
eer
>? hore 1b J! &— rrr Bs * ee
Soe ane
Ke? oo aehe J res er Whe
baggh 2!
me HW
ONL .
A See O36) Fy Lot LP SA ES, Be Gt te . \
Petr ausiyss gees abel oS Pe
A SIMPLE ,COMPARISON h 3
aha, nn ~, Geo) sib Neo
states assume that you have 3 algorithms fo sort alist
=nibgen orb of leg ase
oy, \
“= =n sede DY NSU Sled 1 Meg cay dF
> = hin) =n?
uy — hn) rh
97 sy & Lets also assume that each step takes 1 microsecond (10° “e
ay Which one is better? opt
=z 2 & yr
vy ri aye eo vee een tenn DS pes
oS 17s 28hous 31.7 yeas S gs
OT we
Oe pve pee ye Nie Yes Nal oy Yeas?
wa9r8
ae ANA Segal ns SPs! Coe
yr BNW 1 ep* yoae Cee Ww PL, erowe ak —
wseronooe® eb 4) le 6 PS oP \ ows Spee
- cog ba 3 Aim gs or ee
aS pr pore
pohos
vs 6 n= poss
/ a
pom we feb ELS |
oD se
SO
wed MN 7 ko = -
“ “he jab 6 yee TD SS
Oh Nv buys Ce Syuos #
TT ) 2, weve C1
° Fo 7 BU EM or og SE Be 2) oo" |
. ayerk, “\ po ou speedn, B oe cat COE sve,
“ASYMPTOTIC ANALYSIS >”
oo
s i
sdoseye MMe Re tce SSP Ve Sy Ea§ pipe | Sys
ad. ‘gid yo sped
" itis not typically necessary to know the exact growth function for an algorithm
Finding the exact complexity, f(n) = number of basic operations, of an
algorithm is difficult a
We are mainly interested in the asymptotic complexity of an algorithm — the
general nature of the algorithm as n increases
ee
Asymptotic analysis of an algorithm describes the relative efficiency of an
algorithm as n gets very large.
When you're dealing with small input size, most algorithms will do
When the input size is Very large) things change
(JE.g. : For very large n, algorithm 1 grows faster than algorithm 2. _ ASYMPTOTIC ANALYSIS-
CONT.
(We focus on describing the growth rate of a given function,
say f
(We compare the growth rate of f to the growth rate of some
| | other function, say g
} SB 9
tl | |
[We use asymptotic notations to describe the growth rate(ott )
in terms of g ———
O wi
oi >
call 2 ASYMPTOTIC NOTATIONS
Commonly used asymptotic notations to calculate the running time complexity of an
algorithm.
{20 Notation. O(expression) gives an(upper bound)on the growth rate of a function.
A function f<0(g) means, f grows at most as fast as g, asymptotically and up to a constant
(9) g g, asymp! ly ip
factor. - Yb ==
=
(20 Notation. A(expression) gives the growth rate of a function.
A function fe(g) means f grows, asymptotically, atleast as fastas 9. ys\ &
atleast as fast as 9
{20 Notation. @(expression) consist of all the functions that lie in both O(expression) and
(expression). A function ft
VAs
ww? ae ne 2?
“vom
con a
‘ rg ame
geneva gern E
4 yee
ser
pM
pv Sorrnleisianta Gyw dl bch NO" oe
Ys) aba \ower aS bMS
owed bia Ome) A
ed ot Sv Ue wee DV LABIFY Der See
oe {SN GH)
fock
lovey DY ON %
ner 2 AED gee sy) VS ck ASL [oer dn pert ce aise
vite or” C 2 -
gpl Borge Ore 535d 94 Feo
spews ee ee lone ther BIG-O NOTATION: DEFINITION
< < iz
Big 0: }2\ 2b ges wo 7 el ole (ere
£(n) = O(g(n)) if there are positive constants c and N such that
f(n) sc gin) wi when n= Nuys V2 pet 2 i Sa CO
This says that furetion itn) fows fe arate no faster than g(n) ; thus g(n) is erupper )
Coaungion te), soe Ne ass
uke ih Ge ps wh
Another aie; Hay is O(g(n))~ there exist numbers ©, N> 0 nw
ye such that for each n= N Sa, wad >
HK Py? 1(n) = eBginy
4. Ce) FAemeanina —=—> 7
gy + fin)is larger than g(n) only for finite number of n's; o
559 | + a constant cand a value canbe found so that for every valve of n= N: Ar) $e
+ fin) does not grow more than a constar faster than gin). BIG-O NOTATION:
ILLUSTRATION
cba
fin f{n) = O(¢(n)) Bell He Sy wee
Dip DAM 93.2 S72 24 OF
CLD Up? a8. vee Le
So Kayekor.
Pie KOLO two ‘fel
J ASL 9 P
BIG-O Prove that 7n°+2n2 = O(n3)
- —Since 7n3+2n%$)7n3+2n3 = 9n3 (for n21)
NOTATIO | then 7n%+2n2=0(85) with o=9 and N=1
High ce PMye sige Oe? Jp Se
N : SA Argel ron nesta peleior Ni oG\ ket
EXAMPL E ‘Similarly. we can prove that 7n°+2n2 vr
However, the first bound istighter> )
Serva 96 .
2 2 s. -
Aare h teat aan y p> ack
teehe
$220 Locrlae 20 kr Atehuf rue ae an
ann ‘ni 3399 = Dapper) ephak ”
P: °
4p > ati OF RN 2
42508 OCS) sae erehy
wp ee Ah te" “ZC «
oe
Lie act eos
ede S 4? xen a2 Qa
(SR UY ae
flew Bye gree oe
poe? VP C AA
Now Y7 (aw aaste aeydte cole e
apps 378 BO Dh) peat coe
. Be 2 sno ei
Bnew wh 0 Made BIEPL upset ora OF
BES CONE Sa? “ TIGHTER
UPPER BOUND
Pero EE -
‘Number of Input Items 12 Bo
2 oe AA\
BIG-Q NOTATION: DEFINITION
<->
Big Omeas oT yh
ee De
fin). = 9(g(n)) if there axe\positive constants)¢ and N such
that f(n) 2c g(n) when n= - ee
This says that function f(n) grows at a rate no slower than g(n) ; thus g(n) is a
lower bound on fin). \yebation 8 ¢ gesceriie DN Gites ever
SAS DION ch>
f(n) is Q(g(n))* there exist numbers c, N> 0
Another way;
such that for each n = N
f(n) = cA g(n) Fin)
BIG-Q
NOTATION:
ILLUSTRATION
An) = Q(g{n))
egin)
nd n ec5iN Lge aig oY oe
es ADT 6 pty LMNs COL
pea a OLEH EG
ev
Prove that
(n?)
— Since
AntbnrtzCrr
Be Zon C22
imilarly, we can prove that 2n+5n? = §](n) \
c 4
The first bound igltighter} aorta - Cw")
2
3 Pez o Gye ele w
me 2 tw Se (oes Lu xoe “aad
2 we Pal 4 ye aa NE SSF! 6 U chs ehavior J! >
Ye eS
Tla)=20-+8i0 / /
: / / =n
TIGHTER
LOWER BOUND
&
5
2
‘Number of Input Items N’ | BIG-© NOTATION: DEFINITION
Big Theta:
£(n) = 0(g(n)) if and only if
and £(n) = 9(g(n))
This says that function f(n) grows at the same rate as g(n) .
Another way: -
f(n) is O(g(n))* there exist numbersCi, Cs, N> 0
Yo = acer such that for eac Cn = NS
w)y= <4? f
‘ ws agin) s_ fin) s eljgin)
&
Cdr eer’ ro }
big-0 notation big-O notation YeP%r bound we OF 21} OAD
«
Y
lowes Yoound.
Bates de Ors
pia, IG?
ower upper
1. 0
O:4 2nesn? = alr
t -4
Oe sap aaron cod a a
x99 < 2
a a a eN —- 2p" sans bi 2!
sae? Wr mee ae 3
° av einer “6 Tn SG nr 2 ECR)
Qn KGW Ze BY,
a ae siges
Zo
Shick vp porbor |
LO) ys a PE
bigd Sane o™
Biglnenoa
‘s| Definition: 3K
» EOD gyi a seme ; Gwe NIT ys
Pe! LITTOE hs Qita)rendinn#ca
sxvick uprer’ Cee a
Dourd 3 Pots wo
pyre \iHle OL vy Oey ae!
OW — constad
wen Sp wos \8 Ca> wl nee
XK
oF privkle) “Nak Bate
wewe
{ a
Pac izo ——» 20 ra
cn) pale
So% =. -
Saabs wall $5 de)
DP Ge Wella" e ore
Sat PD oe
Ce!
Jt UY ne
= 256
OC 1e8 |
J rn)
Gul
ae
lon
lo
0 sek
@
$ copra de
~ ease 3 s
Sree
(loa 64) *
(6) =
= 36 oats ee
5,0" y
o(1)—> \0000°° eonstant os S
109 178109 &! otogtogn) 3° iogathmcoregiogn,
‘CATEGORIES | oro —s
ute! Of(lag n}*) oF Oflog'n( poly-logarithmic
Some Big-Oh categories onto) eae
po 2/9 Ln ‘near
aoe tocar oon @F a5
Orr a won BOF * © —_
Loan > Le a log n) _Ahadratic logaritygpic >
PoP goss ee Fwd }
PSS ot EN ee Brrr a a
ve i $ oe") ‘natural exponential ~
eS co woven
Se A 7 Sy Coral) we ‘actoial) aa yt
ae oS 2 Sr? ; See 2° ro | gameersoen z RULES FOR USING BIG-O
For large values of input n, the constants and terms with lower degree of n
9 d p k 9 cle
are ignored. 2 AN Coat VOB
{.Multiplicative Constants Rule: Ignoring constant factors. "
4
O(6 f(n)) = ovine cis constant =”
Example: y
c Cary
(20 n*) = O(n?)
L
Ss ae wwe 4
“i oan» oh Bh BU one
cee Neon ae gt pone’,
ey v = WS get vy GE
oe ? 2. Addition Rule: Ignoring smaller terms.
DEE O(£(n)) < O(R(n)), then O(E(a) + (my) =
o(h(n)).
Qi-e. I£ T,(n) = O(£(n)) and T,(n) = O(g(n)), then
>,« RULES.
de yd T(n) + Ta(n) = max(O(£(n)), O(g(n)))
FOR 225 cxampte
LAs 0 (nF log n +n) = O(n?)
BIG-O- °°
- - do! Example 2 (Algorithm A):
CONT §] congas Step 1: Run algorithm Ay that takes O(n) time
"3, Gus
Step 2: Run algorithm Ae that takes O(n?) time
ee ~ Ta{n) = Tas(n) + Taa(n) = O(n?) + O(n?) = max (O(n"),
OS 49) On4p= O18) 3k os
y) ; 4 Ce wat 131 ae
er PONY onl UB, OV OF
BEND Ur cil asp Qe OG yr OL BYOrb ox
o(”) re
ol) . few Pen oC -9) LT.
Yn O(n? te ow * ee yee
ioe SEZ? ole) DY Coe oss
3. Multiplication Rule:
es t ~ RULES a ee
yo Z , FOR O(gin)), then
peek USING Ti(n) * T2(n) = O(£(n)) * O(g(n))
oO
OY BIG-O- | exame
CONT. O(n + 2n? + 3n log n + 7) (82 + 5n + 2))
O(n5) bo WS? BA OH SES
R U L E S 4. If T(n) is a polynomial of degree k, then
FOR T(n) = O(n*)
USING i neerre tree
BIG-O- OP nw
log¥(n) = O(n) for any
CONT. ‘A
&
ook >» Ex Gootlenty Yo 5.9 CUE gs we
COMPARING GROWTH ean -
FUNCTIONS 77 224 3 om au (gy A
i ibo
a) vi aig) lh SC le Sy OG Roloe sh sl SL Bike Seah 7
\3u. You might think that faster processors would make efficient algorithms less
ee
g a4
co
important
A faster CPU helps, but not relative to the dominant term
Algorithm | Time Complexity | Max Problem Size | Max Problem Size
Before Speedup _| After Speedup
Sp Be J we5ig Serr
opera ov COMPARI
NG
GROWTH .,
FUNCTIO,,
NS-”
A hierarchy of growth rates:
SF
> Pooge
\
mou)
5 6 < logan
og < 1
af nl <
\e
< logan < log?n <
nlogen « n? < n? < 29 <
~seY
ntogen :
we we NP
s a
Bl del Flog o! COMPARIN
G
GROWTH
FUNCTION .
S-CONT. ~—
growth functions diverge
dramatically
. "
\o4) JN oe
re EXAMPLE CO us
ope wo
Let f(n) =n log(n) and g(n) =n" %
“Which grows faster?> nlogn " 5
: a : WSs
& pe Mowe
login 2H Loon
x g@(n) grows faster than f(n).
tL rags SARE S Te * . WD
ga) mleg wd geyeaw nla
_ Mlegn wn
a
wv leq a eo woe
vel pcb Zz
D oles is
Sinise Casber®? loan
bx) BA et aes Ue 2 AN OT H E R We can always determine the relative growth
rates of two functions f and g by computing ,
U S E F U L invoking L'Hopital’s rule if necessary
then f(n) = o(g(n))
TECHNIQ 2)ifL =, then f(n) = Z(g(n)) a >
Pager;
UE | DIFL = then (0) = Of oppor Ceig fh
oO ved w . ae
CYB t Gus \wn DP Spray © oly Ag>
wat
wot?
A “5 on
Z
y
EXAMPLE
Then tim &
Neves gin)
= lim7 ++
now "in
= 7+ lim+
mh
So, f{n) = O(n?) + ¥C re a Cet ) DETERMINING THE
COMPLEXITY OF SOME CODE
STRUCTURES w 220 Conplaty 5 SAP)
In general,
9 WS VGaMede\ ooo Do PE
x doing something with every item in one dimension is linear (© Oo)
209 V0 — ()
* doing something with every item in two dimensions is quadratic, and 0
x dividing the working area is logarithmic (of the divisor) O (\e +)
: py a2) \
nergy ere S$ 497
ey ak og
et > Analyzing Loop Execution
se -
[ee of el azdo ess! pase Sy'2>
Se
Loops: for, while, and do-whil
- Loops complexity is determined by the number of iterations in the loop multiplied by
the complexity of the body of the loop
- Loop complexity = Number of iteration x Body complexity
ASU ere
- Examples:
okt ew
Number of loop executions = 7
Bed rece oc | gosly complenity = OX1)
//some sequence of 0(1) steps
ikem awh ais?
ele
oh
for (int i = 0; i
=xry;? “Dgor(int ick; icen; isitm)
ali] =x * ye - hy. ( 7 ot
ot\ze2se0 2 2 &* & ¥ statement];
yryt ati 1 statement2;
, } sw! Bao ©
GOP FIN Soe SG See NED [Er Le apace &
Loops with logarithmic Iterations: 1 EO Bet Ly a @
~ Loops that iteratively divide the work space ee a logarithmic Tunning time
- Examples: wey Y
NO BF SRetzap Ble)
for (int tsk dea eet Toa epee 5
/fsome sequence of 0(1) steps i \. “:
Kare es
for (int isky bem isi te peslog Gap
//sone sequence of 0(1) steps 9 ize y
a»
eC ley n)
for (int L= 0; i< np 4=]i* 2)
Tone sequence of O(1) steps = map |_O(logn)
Bae
gre tor,
oe of ‘o> THE MODEL
To analyze algorithms in the formal framework, we need a model
of computation.
Our model has the standard set of simple instructions including
addition, multiplication, comparison, and assignment. We
assume:
{it takes one time unit to do anything simple. This is not entirely realistic
since not all operations take the same amount of time.
{We have infinite memory. This won't consider effects like page faults “ THE MODEL- CONT.
The most important resource to analyze is the funning time.
(We will not model the compiler and computer, although they affect
the results.
instead, we focus primarily on the algorithm (not necessarily the
program) and the input to the algorithm. Typically, the size of the
Oa
input (n) is the main consideration. ie THE
MODEL-
CONT.
-We define two functions, Tavg (n) and Tworst (M)
as the average and worst-case running time of
the algorithm. Generally, the quantity required is
the worst-case time, since this provides a bound
for all input.
“The average running time is much harder to
compute, let alone define.
For example, what is the “average” input to the algorithm?
This is not always well defined ANALYZIN
G LOOP
EXECUTI
ON
Loops: for, while, and do-while:
First determine the order of the body of the loop, then
multiply that by the number of times the loop will ;
execute eo
for (int count = 0; count < n;
count++)
// some sequence of 0(1) steps
N loop executions times O(1) operations results in a
O(n) efficiency 1
Consider the following loop: J, id
count = 1; \
while (count < n)
{
count *= 2;
// some sequence of 0(1) steps
}
The loop is executed logon times, so the loop is O(log
n) ae
ANALYZING LOOP_ “2, Oe
EXECUTION- CONT. “3° her ©
g
Loops: for, while, and do-while: Lot
ration®in the loop times multiplied by
AP Hee SSS le AE
foe OF
Dgai:compeny i detarsned by he nur
aN
be complexity of the body of the loop.. Co exe
ge 8
Exmnples:
wae
9
O(n)
~ Cae)
Ch) ows °
7° = ox Co b2Cm +LCn
2, ae wane!
a pe +H my OLn)
en cd - pane
x\ alttey) a
BBcH@
ANALYZING LOOP. 2\2 0 922 c
wise &
SSG a Joler fly ayo ode J
EXECUTION- CON “ Sint
Loops: for, while, and do-while: §— —=—yer
ae LU
Se
Again: complexity is determined tore rStates in the loop times wes abe US let ~ aie
the complexity of the body of the loo}
soeaitg sorelenty oy p.
C GEN ody St pth
2% Examples: ot
5
O(log n)
js WH ahagrith 5 analysis jules
aasorip oie Hs Db Joos" BY YE OND ailn fear CoD Gate oat 7 BD 2
Weeds CIF
VA C8 Seas B) Lae BD LURE oa, timer J
FEA DFA Biss al comple! 5 oll behic Gel aA gach _
vosicopain GmanGi C le
20 perebon in Srey 2¢
cSeospaeei) 5c. COND
2 ‘aa?
/ _
Vleet te Consted ge se YC AS pte! total AI Tsp, ee
=> O() joe
go bor
cuca (is acolk 2 vig?
Se (wr ie Scop \O4 x|s oe
oh o(\oa))
a or
2 a
2 ea Gs»
3 ey oa ve
Soclay Tas omeneste
1 operation oF
atest (i 2.n operations |
the loop body that has three assignments, two
multiplications, and an addition- 6 n operations
Thus, the total number of basic operations is
6*nt+2*n+(n+1)+3= 9nt4 ANALYZING LOOP
EXECUTION- CONT. cen
Analyzing Nested Loops: - Loop complexity = Complexity of inner loop x complexity of outer loop
When loops are nested, we multiply the complexity of the outer loop by the
complexity ofthe innerloop yy,
for (int count = 0; count < nj countt)
for (int count2 = 0; count? < nj count2++) ep
mp ¢
o>
J) some sequence of 0(1) steps
} ok
Both the inner and outer loops have complexity of O(n)
The overall efficiency is O(n?) ANALYZING LOOP Ne
EXECUTION- CONT. kore
Examples: | ANALYZING LOOP
EXECUTION- CONT. »)'s0) <2 aye"
Nested Loops: Complexity of inner loop * complexity of outer loop <5; ate! aur 2! Ld
: G
Example: nye ” Consecutive statements: Use Addition rule
[These just add, and the maximum is the one that counts
O(81, 824 ay = s88) = Of) 4, O(82) + O(a) + = + O(BA)= O(MAR(S1, 82, 83+
Sk)) es nt
Bramley ere )
\ \ -
S . Poa
7 75m) a
On, ca
ga PRD wywed ek
SYN Complexity is Of62) Bin) + O(1) = O(n?) = of x) —) ANALYZING SEQUENCE OF
STATEMENTS- CONT.
Consecutive statements: Use Addition rule
Example: (25x
ww = O(n)
»
O(n?)
4 Aloe
Beomplexy is O(n? +n) = O(n’) ANALYZING SEQUENCE OF
STATEMENTS- CONT.
Consecutive statements: Use Additiqn zule,
Example: ~
O(n?)
(1)
O(n)
O(n)
Qn? +44 +n n= O(n? +.2n + 1) = O(n) ZH 7 C8 OSD) —— a byarcbine) sis
5S -elsé
op ond SH
| ANALYZING I F EXECUTION Yoi9 3! Ga ae’ ON 53
aes . wigo DCs 2154
wee L a “ re
If Statement: Take the complexity of the oor ami con : oe woot
char Key; . ow) ot)
sitio scom ummm (ct D* |.) On
Ane] 0) © = new int) fo}; ey en 5 oo
fg 2)! Pe PS oC”)
i
To determine the order of the loop body, the order of the method must be vs en
considered
The overhead of the method call itself is generally ignored
\
> Lv
IPN) a2 apt UF ANALYZING METHOD CALLS- CONT. = \oy
lege Klevn =
Loop example:
Suppore sa multiple of 2, Determine the umber of bask operations porfored by of tho
1d myMethod|
Hence the numberof basic operations i
VETS (ogi) ogi TT (oe) faba Ce
= 4 login + logynf10 + Sn] +1 = Snlegin +11 login 4-4 = Olalogn) ANALYZING METHOD CALLS- CONT.
ya) op
Recursion:
* Analyze from the inside (or deepest part) first and work outwards. If there are function calls,
these must be analyzed first.
Example:
What about the function call?
o'
«The running time of factorial{n) = rn) = 2 + Tin-1) =
44 T(n-2) = 6 + T(n-3) =.
2n = O(n) EXAMPLES OF ALGORITHMS
yee
e
on) ‘Accessing an array element
AND THEIR BIG-O
COMPLEXITY a
Push, Pop, Enqueve (if there is a tall reference), Dequeue,
ao
Otlogin)) Fes Binary search <<
Gof evden SN ee ev
De S22
O(n)
LAE Gis SH
ay 9
O(n foginy)
Heap sort, Quick sort (average), Merge sort
ee
s
be! OF hot
4 Selection sot, Insetn sr, Bubble sor A
O(n") Matrix mutpication eel ol op wel
ow oo
ce) Tones tne app
ght Review of Common Order-of-Growth Hypotheses
ih Poa core Co
as statement ae
(1) constant 5 oidoee
white (> D divide
(log n) logarithmic qlee Ee 5 ere inary search
for (int 4 = 0; 4
