ANALYSIS OF ALGORITHMS - Purdue University

1 1 ANALYSIS of AlgorithmsANALYSIS OFALGORITHMS Quick Mathematical Review Running Time Pseudo-Code ANALYSIS of ALGORITHMS Asymptotic Notation Asymptotic Analysisn= 4 AlgorithmInputT(n)Output2 ANALYSIS of AlgorithmsA Quick Math Review Logarithms and Exponents- properties oflogarithms:logb(xy) = logbx + logbylogb(x/y) = logbx - logbylogbx = logbxlogaxlogab- properties ofexponentials:a(b+c) = abacabc = (ab)cab/ac = a(b-c)b = abc = alogba=logabc*logab3 ANALYSIS of AlgorithmsA Quick Math Review (cont.) Floor x = the largest integer x Ceiling x = the smallest integer x Summations- general definition:- wheref is a function,s is the start index, andt isthe end index Geometric progression:f(i)=ai- given an integern 0 and a real number 0 <a 1- geometric progressions exhibit exponential growthfi()is=t fs()fs1+()fs2+().

2 Ft()++++= + 1a ---------------------=++++=i0=n 4 ANALYSIS of AlgorithmsAverage Case vs. Worst CaseRunning Time of an Algorithm An algorithm may run faster on certain data setsthan on others, Finding theaverage case can be very difficult, sotypically ALGORITHMS are measured by theworst-casetime complexity. Also, in certain application domains ( , air trafficcontrol, surgery) knowing theworst-casetimecomplexity is of crucial InstanceRunning Time1 ms2 ms3 ms4 ms5 msABCDEFG worst-casebest-case}average-case5 ANALYSIS of AlgorithmsMeasuring the Running Time How should we measure the running time of analgorithm? Experimental Study- Write aprogram that implements the algorithm- Run the program with data sets of varying size Use a method () to getan accurate measure of the actual running The resulting data set should look something like:501000t(ms)n1020304050606 ANALYSIS of AlgorithmsBeyond Experimental Studies Experimental studies have several limitations:- It is necessary toimplement and test the algorithmin order to determine its running Experiments can be done only on alimited set ofinputs, and may not be indicative of the runningtime on other inputs not included in In order to compare two ALGORITHMS , the samehardware and software environments should beused.

3 We will now develop ageneral methodology foranalyzing the running time of ALGORITHMS that- Uses ahigh-level description of the algorithminstead of testing one of its Takes into accountall possible Allows one to evaluate the efficiency of anyalgorithm in a way that isindependent from thehardware and software of AlgorithmsPseudo-Code Pseudo-code is a description of an algorithm that ismore structured than usual prose but less formal thana programming language. Example: finding the maximum element of an arrayMax(A,n):Input: An array A storingn : The maximum element in A[0]fori 1ton 1doifcurrentMax < A[i]thencurrentMax A[i]returncurrentMax Pseudo-code is our preferred notation for describingalgorithms. However, pseudo-code hides program design of AlgorithmsWhat is Pseudo-Code?

4 A mixture of natural language and high-levelprogramming concepts that describes the main ideasbehind a generic implementation of a data structureor Expressions: use standard mathematical symbolsto describe numeric and boolean expressions- use for assignment ( = in Java)- use= for the equality relationship ( == in Java)- Method Declarations:-Algorithm name(param1,param2)- Programming Constructs:- decision [ ]- while- do- repeat- until ..- for-loop:for .. do- array indexing:A[i]- Methods:- calls:object method(args)- returns:return value9 ANALYSIS of AlgorithmsA Quick Math Review (cont.) Arithmetic progressions:- An example- two visual ++++=i1=n n2n+2---------------=1n/2012n32n+ of AlgorithmsAnalysis of ALGORITHMS Primitive Operations: Low-level computations thatare largely independent from the programminglanguage and can be identified in pseudocode, :- calling a method and returning from a method- performing an arithmetic operation ( addition)- comparing two numbers, etc.

5 By inspecting the pseudo-code, we cancount thenumber of primitive operations executed by analgorithm. Example:Algorithm arrayMax(A,n):Input: An array A storingn : The maximum element in A[0]fori 1ton 1doifcurrentMax < A[i]thencurrentMax A[i]returncurrentMax11 ANALYSIS of AlgorithmsAsymptotic Notation Goal: To simplify ANALYSIS by getting rid ofunneeded information- Like rounding : 1,000,001 1,000,000-3n2 n2 The Big-Oh Notation- given functions f(n) and g(n), we say thatf(n) isO(g(n)) if and only iff(n) c g(n) forn n0- c andn0 are constants, f(n) and g(n) are functionsover non-negative integersInput SizeRunning Timecg(n)f(n)n012 ANALYSIS of AlgorithmsAsymptotic Notation (cont.) Note: Even though 7n-3isO(n5), it is expected thatsuch an approximation be of as small an order aspossible.

6 Simple Rule: Drop lower order terms and - 3 isO(n)-8n2logn + 5n2 +n isO(n2logn) Special classes of ALGORITHMS :- logarithmic:O(logn)- linearO(n)- quadraticO(n2)- polynomialO(nk), k 1- exponentialO(an),n> 1 Relatives of the Big-Oh (f(n)): Big Omega (f(n)): Big Theta13 ANALYSIS of AlgorithmsAsymptotic ANALYSIS of TheRunning Time Use the Big-Oh notation to express the number ofprimitive operations executed as a function of theinput size. For example, we say that thearrayMax algorithmruns inO(n) time. Comparing the asymptotic running time- an algorithm that runs inO(n) time is better thanone that runs inO(n2) time- similarly,O(log n) is better thanO(n)- hierarchy of functions:- log n << n << n2<< n3<< 2n Caution!- Beware of very large constant factors.

7 Analgorithm running in time 1,000,000nis stillO(n)but might be less efficient on your data set thanone running in time 2n2, which isO(n2)14 ANALYSIS of AlgorithmsExample of Asymptotic ANALYSIS An algorithm for computing prefix averagesAlgorithm prefixAverages1(X):Input: Ann-element arrayX of : Ann-element array A of numbers such thatA[i] is the average of elementsX[0], .. ,X[i].Let A be an array ofn 0ton - 1doa 0forj 0toidoa a +X[j]A[i] a/(i + 1)return array A ANALYSIS ..15 ANALYSIS of AlgorithmsExample of Asymptotic ANALYSIS A better algorithm for computing prefix averages:Algorithm prefixAverages2(X):Input: Ann-element arrayX of : Ann-element array A of numbers such thatA[i] is the average of elementsX[0], .. ,X[i].Let A be an array ofn 0fori 0ton - 1dos s+X[i]A[i] s/(i + 1)return array A ANALYSIS .

8 16 ANALYSIS of AlgorithmsAdvanced Topics: SimpleJustification Techniques By Example- Find an example- Find a counter example The Contra Attack- Find a contradiction in the negative statement- Contrapositive Induction and Loop-Invariants- Induction- 1) Prove the base case- 2) Prove that any casen implies the next case (n + 1) is also true- Loop invariants- Prove initial claimS0- Show thatSi-1 impliesSi will be true after iterationi17 ANALYSIS of AlgorithmsAdvanced Topics: OtherJustification Techniques Proof by Excessive Waving of Hands Proof by Incomprehensible Diagram Proof by Very Large Bribes- see instructor after class Proof by Violent Metaphor- Don t argue with anyone who always assumes asequence consists of hand grenades The Emperor s New Clothes Method- This proof is so obvious only an idiot wouldn t beable to understand it.

9