CCS 3102 Lecture 3_ Complexity theory.pdf

presentation on data analysis and algorithms

1. Design and Analysis of
Algorithms
Complexity theory
Department of Computer Science

2. Complexity theory
❖The complexity of an algorithm is simply the
amount of work the algorithm performs to complete
its task.
❖Complexity theory is the study of the cost of
solving interesting problems. It measures the
amount of resources needed.
Time
Space
❖Two aspects
Upper bounds: give a fast algorithm
Lower bounds: no algorithm is faster.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 2

3. What is Algorithm Analysis?
❖How to estimate the time required for an
algorithm
❖Techniques that drastically reduce the
running time of an algorithm
❖Amathemactical framework that more
rigorously describes the running time of an
algorithm
Monday, March 6, 2023 3Design and Analysis of Computer Algorithm

4. Algorithm Analysis(1/5)
❖Measures the efficiency of an algorithm or its
implementation as a program as the input size
becomes very large
❖We evaluate a new algorithm by comparing its
performance with that of previous approaches
Comparisons are asymptotic analyses of classes of
algorithms
❖We usually analyze the time required for an
algorithm and the space required for a
datastructure
Monday, March 6, 2023 4Design and Analysis of Computer Algorithm

5. Algorithm Analysis (2/5)
❖Many criteria affect the running time of an
algorithm, including
speed of CPU, bus and peripheral hardware
design think time, programming time and
debugging time
language used and coding efficiency of the
programmer
quality of input (good, bad or average)
Monday, March 6, 2023 5Design and Analysis of Computer Algorithm

6. Algorithm Analysis (3/5)
❖Programs derived from two algorithms for solving
the same problem should both be
Machine independent
Language independent
Environment independent (load on the
system,...)
Amenable to mathematical study
Realistic
Monday, March 6, 2023 6Design and Analysis of Computer Algorithm

7. Algorithm Analysis (4/5)
❖Weestimatethealgorithm'sperformancebasedon
thenumberofkeyandbasicoperationsitrequires
toprocessaninputofagivensize
❖ForagiveninputsizenweexpressthetimeTto
runthealgorithmasafunctionT(n)
❖Conceptofgrowthrateallowsustocompare
runningtimeoftwoalgorithmswithoutwritingtwo
programsandrunningthemonthesamecomputer
Monday, March 6, 2023 7Design and Analysis of Computer Algorithm

8. Algorithm Analysis (5/5)
❖Formally,letT(A,L,M)betotalruntimefor
algorithmAifitwereimplementedwithlanguageL
onmachineM.Thenthecomplexityclassof
algorithmAis
O(T(A,L1,M1)UO(T(A,L2,M2))UO(T(A,L3,M3))U...
❖CallthecomplexityclassV;thenthecomplexityof
AissaidtobefifV=O(f)
❖TheclassofalgorithmstowhichAbelongsissaid
tobeofatmostlinear/quadratic/etc.
Monday, March 6, 2023 8Design and Analysis of Computer Algorithm

9. Performance Analysis
❖Predictingtheresourceswhicharerequiredby
analgorithmtoperformitstask.
❖An algorithm is said to be efficient and fast, if it
takes less time to execute and consumes less
memory space. The performance of an
algorithm is measured on the basis of following
properties :
SpaceComplexity
TimeComplexity
Monday, March 6, 2023Design and Analysis of Computer Algorithm 9

10. Input Size
❖Timeandspacecomplexity
Thisisgenerallyafunctionoftheinputsize
▪E.g.,sorting,multiplication
Howwecharacterizeinputsizedepends:
▪Sorting:numberofinputitems
▪Multiplication:totalnumberofbits
▪Graphalgorithms:numberofnodes&edges
▪Etc
Monday, March 6, 2023 10Design and Analysis of Computer Algorithm

11. 11
Running Time
❖Most algorithms transform input
objects into output objects.
❖The running time of an
algorithm typically grows with
the input size.
❖Average case time is often
difficult to determine.
❖We focus on the worst case
running time.
Easier to analyze
Crucial to applications such as
games, finance and robotics0
20
40
60
80
100
120
Running Time
1000 2000 3000 4000
Input Size
best case
average case
worst case
Design and Analysis of Computer AlgorithmMonday, March 6, 2023

12. Running Time
❖Numberofprimitivestepsthatareexecuted
Exceptfortimeofexecutingafunctioncall,most
statementsroughlyrequirethesameamountof
time
▪y=m*x+b
▪c=5/9*(t-32)
▪z=f(x)+g(y)
❖Wecanbemoreexactifneedbe
Monday, March 6, 2023 12Design and Analysis of Computer Algorithm

13. Space Complexity
❖Itstheamountofmemoryspacerequiredbythealgorithm,
duringthecourseofitsexecution.
❖Itmustbetakenseriouslyformulti-usersystemsandin
situationswherelimitedmemoryisavailable.
❖An algorithm generally requires space for following
components :
❖InstructionSpace:Itsthespacerequiredtostoretheexecutableversion
oftheprogram.Thisspaceisfixed,butvariesdependinguponthe
numberoflinesofcodeintheprogram.
❖DataSpace:Itsthespacerequiredtostorealltheconstantsand
variablesvalue.
❖EnvironmentSpace:Itsthespacerequiredtostoretheenvironment
informationneededtoresumethesuspendedfunction.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 13

14. Constant Space Complexity
intsquare(inta)
{
returna*a;
}
❖Ifanyalgorithmrequiresafixedamountof
spaceforallinputvaluesthenthatspace
complexityissaidtobeConstantSpace
Complexity
Monday, March 6, 2023Design and Analysis of Computer Algorithm 14

15. Linear Space Complexity
intsum(intA[],intn)
{
intsum=0,i;
for(i=0;i<n;i++)
sum=sum+A[i];
returnsum;
}
❖Iftheamountofspacerequiredbyanalgorithmis
increasedwiththeincreaseofinputvalue,thenthat
spacecomplexityissaidtobeLinearSpace
Complexity
Monday, March 6, 2023Design and Analysis of Computer Algorithm 15

16. Time Complexity
❖Thetimecomplexityofanalgorithmisthetotal
amountoftimerequiredbyanalgorithmto
completeitsexecution.
❖Ifanyprogramrequiresfixedamountoftimefor
allinputvaluesthenitstimecomplexityissaid
tobeConstantTimeComplexity
intsum(inta,intb)
{
returna+b;
}
Monday, March 6, 2023Design and Analysis of Computer Algorithm 16

17. Linear Time Complexity
❖Iftheamountoftimerequiredbyanalgorithmis
increasedwiththeincreaseofinputvaluethen
thattimecomplexityissaidtobeLinearTime
Complexity
Monday, March 6, 2023Design and Analysis of Computer Algorithm 17

18. Asymptotic Performance
❖Howdoesthealgorithmbehaveasthe
problemsizegetsverylarge?
Runningtime
Memory/storagerequirements
Bandwidth/powerrequirements/logicgates/etc.
Monday, March 6, 2023 18Design and Analysis of Computer Algorithm

19. Order of Growth
❖This refers to the rate of growth of the running time
of an algorithm
❖Only the leading term of a formula that matters
since the lower-order terms are relatively
insignificant for large n
❖E.g. given an
2
+bn+cfor some constants a, b and
c, the leading term is an
2
❖We also ignore the leading term’s constant
coefficient since it has less significant than the rate
of growth. Hence we write Ɵn
2
(“theta of n-
squared”)
Monday, March 6, 2023Design and Analysis of Computer Algorithm 19

20. Rate of Growth
❖Considertheexampleofbuyingelephantsand
goldfish:
Cost:cost_of_elephants+cost_of_goldfish
Cost~cost_of_elephants(approximation)
❖Thelowordertermsinafunctionarerelatively
insignificantforlargen
n
4
+100n
2
+10n+50~n
4
i.e.,wesaythatn
4
+100n
2
+10n+50andn
4
havethesamerateofgrowth
Monday, March 6, 2023Design and Analysis of Computer Algorithm 20

21. Function of Growth rate
Monday, March 6, 2023Design and Analysis of Computer Algorithm 21

22. Asymptotic notation
❖Asymptoticefficiencyofalgorithmsiswhenwe
lookatinputsizeslargeenoughtomakeonly
theorderofgrowthoftherunningtimerelevant
❖Studyinghowtherunningtimeofanalgorithm
increaseswiththesizeofinputinthelimitas
thesizeofinputincreaseswithoutbound
❖Asymptoticallymoreefficientalgorithmisbest
forallbutverysmallinputs
Monday, March 6, 2023Design and Analysis of Computer Algorithm 22

23. Big O Notation
❖BigOnotation:asymptotic“lessthan”:
❖f(n)O(g(n))ifandonlyifc>0,andn
0,sothat
0≤f(n)≤cg(n)foralln≥n
0
❖f(n)=O(g(n))meansf(n)O(g(n))(i.e.,atmost)
Wesaythatg(n)isanasymptoticupperbound
forf(n).
❖Italsomeans:
❖E.g.f(n)=O(n
2
)ifthereexistsc,n
0>0suchthat
f(n)≤cn
2
,foralln≥n
0.
lim ≤ c
n→
f(n)
g(n)
Monday, March 6, 2023 23Design and Analysis of Computer Algorithm

24. Big-Oh Rules
❖Iff(n)isapolynomialofdegreed,thenf(n)isO(n
d
),
i.e.,
1.Droplower-orderterms
2.Dropconstantfactors
❖Usethesmallestpossibleclassoffunctions
Say“2nisO(n)”insteadof“2nisO(n
2
)”
❖Usethesimplestexpressionoftheclass
Say“3n+5isO(n)”insteadof“3n+5isO(3n)”
Monday, March 6, 2023Design and Analysis of Computer Algorithm 24

25. When to use –big Oh
❖Big“oh”-asymptoticupperboundonthegrowthof
analgorithm
❖WhendoweuseBigOh?
1.TheoryofNP-completeness
2.Toprovideinformationonthemaximumnumberof
operationsthatanalgorithmperforms
InsertionsortisO(n
2
)intheworstcase
▪Thismeansthatintheworstcaseitperformsat
mostcn
2
operations
Monday, March 6, 2023Design and Analysis of Computer Algorithm 25

26. Omega Notation
❖notation: asymptotic “greater than”:
❖f(n)(g(n)) if and only if c > 0, and n
0 ,
so that 0 ≤ cg(n) ≤ f(n)for all n≥ n
0
❖f(n)= (g(n)) means f(n)(g(n)) (i.e, at
least)
We say g(n) is an asymptotic lower boundof
f(n).
❖It also means:
lim ≥ c
n→
f(n)
g(n)
Monday, March 6, 2023 26Design and Analysis of Computer Algorithm

27. When to use –Omega
Omega-asymptoticlowerboundonthegrowthofan
algorithmoraproblem
*
WhendoweuseOmega?
1.Toprovideinformationontheminimumnumberof
operationsthatanalgorithmperforms
Insertionsortis(n)inthebestcase
▪Thismeansthatinthebestcaseitsinstruction
countisatleastcn,
Itis(n
2
)intheworstcase
▪Thismeansthatintheworstcaseitsinstruction
countisatleastcn
2
Monday, March 6, 2023Design and Analysis of Computer Algorithm 27

28. When to use–Omega cont.
2.Toprovideinformationonaclassofalgorithms
thatsolveaproblem
Sortalgorithmsbasedoncomparisonofkeysare
(nlgn)intheworstcase
▪Thismeansthatallsortalgorithmsbasedonlyon
comparisonofkeyshavetodoatleastcnlgn
operations
Anyalgorithmbasedonlyoncomparisonofkeys
tofindthemaximumofnelementsis(n)in
everycase
▪Thismeansthatallalgorithmsbasedonlyon
comparisonofkeystofindmaximumhavetodoat
leastcnoperations
Monday, March 6, 2023Design and Analysis of Computer Algorithm 28

29. Theta Notation
❖Θnotation:asymptotic“equality”:
❖Combinelowerandupperbound
❖Meanstight:ofthesameorder
❖&#3627408467;??????∈Θ&#3627408468;??????ifandonlyif∃??????
1,??????
2>0,and??????
0,
suchthat??????
1&#3627408468;??????≤&#3627408467;??????≤??????
2&#3627408468;??????forany??????≥??????
0
❖&#3627408467;??????=??????&#3627408468;??????means&#3627408467;??????∈??????&#3627408468;??????
Wesayg(n)isanasymptoticallytightboundfor
f(n).
❖Italsomeans:
??????
1≤lim
??????→∞
&#3627408467;(??????)
&#3627408468;(??????)
≤??????
2
Monday, March 6, 2023 29Design and Analysis of Computer Algorithm

30. When to use -Theta
❖Theta-asymptotictightboundonthegrowthrate
Insertionsortis (n
2
)intheworstandaverage
cases
▪Themeansthatintheworstcaseandaverage
casesinsertionsortperformscn
2
operations
Binarysearchis(lgn)intheworstandaverage
cases
▪Themeansthatintheworstcaseandaverage
casesbinarysearchperformsclgnoperations
❖Note:WewanttoclassifyanalgorithmusingTheta.
❖Little“oh”-usedtodenoteanupperboundthatisnot
asymptoticallytight.nisino(n
3
).nisnotino(n)
Monday, March 6, 2023Design and Analysis of Computer Algorithm 30

31. Illustration
&#3627408467;??????=??????(&#3627408468;??????) &#3627408467;??????=Ω(&#3627408468;??????) &#3627408467;??????=Θ(&#3627408468;??????)
Monday, March 6, 2023 31Design and Analysis of Computer Algorithm

32. Does 5n+2 O(n)?
Proof:FromthedefinitionofBigOh,theremustexistc>0
andintegerN>0suchthat05n+2cnforallnN.
Dividingbothsidesoftheinequalitybyn>0weget:
05+2/nc.
2/n2,2/n>0becomessmallerwhennincreases
TherearemanychoiceshereforcandN.
IfwechooseN=1thenc5+2/1=7.
Ifwechoosec=6,then05+2/n6.SoN2.
Ineithercase(weonlyneedone!)wehaveac>oandN>0
suchthat05n+2cnforallnN.Sothedefinitionis
satisfiedand5n+2O(n)
Monday, March 6, 2023Design and Analysis of Computer Algorithm 32

33. Is 5n-20(n)?
Proof:FromthedefinitionofOmega,theremustexistc>0and
integerN>0suchthat0cn5n-20forallnN
Dividingtheinequalitybyn>0weget:0c5-20/nforallnN.
20/n20,and20/nbecomessmallerasngrows.
TherearemanychoiceshereforcandN.
Sincec>0,5–20/n>0andN>4
Forexample,ifwechoosec=4,then5–20/n4andN
20
Inthiscasewehaveac>oandN>0suchthat0cn5n-20
forallnN.Sothedefinitionissatisfiedand5n-20(n)
Monday, March 6, 2023Design and Analysis of Computer Algorithm 33

34. Is 1/2n
2
-3nO(n
2
)?
Monday, March 6, 2023Design and Analysis of Computer Algorithm 34

35. . and So
. all for
1/4.c Choose finite for 0 Since
6. Since
.
that such and exist must There
1241
12
3
2
1
4
1
.2/1 ,3
and
3
2
1
00
3
2
1
0
get we0
2
by Dividing
allfor 3
2
2
12
0
00
==
−
=
−
−

−

N/c
n
n
cn/n
N, c
n
c
n
Nnnncn
Nc
N Is 1/2n
2
-3n(n
2
)?
Monday, March 6, 2023Design and Analysis of Computer Algorithm 35

36. Kinds of Analysis
❖Worst case (usually)
Provides an upper bound on running time
An absolute guarantee
❖Average case (sometimes)
Provides the expected running time
Very useful, but treat with care: what is “average”?
▪Random (equally likely) inputs
▪Real-life inputs
❖Best-case:(rarely)
Cheatwithaslowalgorithmthatworksfaston
someinput.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 36

37. Empirical Analysis of Algorithms
❖In practice, we will often need to resort to empirical
rather than theoretical analysis to compare algorithms.
We may want to know something about performance of
the algorithm “on average” for real instances.
Our model of computation may not capture important
effects of the hardware architecture that arise in
practice.
There may be implementation details that affect
constant factors and are not captured by asymptotic
analysis.
❖For this purpose, we need a methodology for comparing
algorithms based on real-world performance.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 37

38. Issues to Consider
❖Empirical analysis introduces many more factors
that need to be controlled in some way.
Test platform (hardware, language, compiler)
Measures of performance (what to compare)
Benchmark test set (what instances to test on)
Algorithmic parameters
Implementation details
❖It is much less obvious how to perform a rigorous
analysis in the presence of so many factors.
❖Practical considerations prevent complete testing.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 38

39. Measures of Performance
❖For the time being, we focus on sequential
algorithms.
❖What is an appropriate measure of performance?
❖What is the goal?
Compare two algorithms.
Improve the implementation of a single algorithm.
❖Possible measures
Empirical running time (CPU time, wallclock)
Representative operation counts
Monday, March 6, 2023Design and Analysis of Computer Algorithm 39

40. Measuring Time
❖There are three relevant measures of time taken by a
process.
User time measures the amount of time (number of
cycles taken by a process in “user mode.”
System time the time taken by the kernel executing on
behalf of the process.
Wallclocktime is the total “real” time taken to execute
the process.
❖Generally speaking, user time is the most relevant,
though it ignores some important operations (I/O, etc.).
❖Wallclocktime should be used cautiously/sparingly, but
may be necessary for assessment of parallel codes,
Monday, March 6, 2023Design and Analysis of Computer Algorithm 40

41. Representative Operation Counts
❖In some cases, we may want to count operations, rather
than time
Identify bottlenecks
Counterpart to theoretical analysis
❖What operations should we count?
Profilers can count function calls and executions of
individual lines of code to identify bottlenecks.
We may know a priori what operations we want to
measure
(example: comparisons and swaps in sorting).
Monday, March 6, 2023Design and Analysis of Computer Algorithm 41

42. Test Sets
❖It is crucial to choose your test set well.
❖The instances must be chosen carefully in order to allow
proper conclusions to be drawn.
❖We must pay close attention to
their size,
inherent difficulty,
and other important structural properties.
❖This is especially important if we are trying to distinguish
among multiple algorithms.
❖Example: Sorting
Monday, March 6, 2023Design and Analysis of Computer Algorithm 42

43. Comparing Algorithms
❖Given a performance measure and a test set, the
question still arises how to decide which algorithm is
“better.”
❖We can do the comparison using some sort of summary
statistic.
Arithmetic mean
Geometric mean
Variance
❖Performance profiles allow comparison of algorithms
across an entire test set without loss of information.
❖They provide a visual summary of how algorithms
compare on a performance measure across a test set
Monday, March 6, 2023Design and Analysis of Computer Algorithm 43

44. Accounting for Stochasticity
❖In empirical analysis, we must take account of the fact
that running times are inherently stochastic.
❖If we are measuring wallclocktime, this may vary
substantially for seemingly identical executions.
❖In the case of parallel processing, stochasticity may also
arise due to asynchronism(order of operations).
❖In such case, multiple identical runs may be used to
estimate the affect of this randomness.
❖If necessary, statistical analysis may be used to analyze
the results, but this is beyond the scope of this course.
Monday, March 6, 2023Design and Analysis of Computer Algorithm 44

45. Empirical versus Theoretical Analysis
❖For sequential algorithms, asymptotic analysis is often
good enough for choosing between algorithms.
❖It is less ideal with respect to tuning of implementation
details.
❖For parallel algorithms, asymptotic analysis is far more
problematic.
❖The details not captured by the model of computation
can matter much more.
❖There is an additional dimension on which we must
compare algorithms: scalability
Monday, March 6, 2023Design and Analysis of Computer Algorithm 45