Algorithm/Running Time AnalysisRunning TimePseudo-CodeMath ReviewCounting OperationsAsymptotic NotationBig-OhExamplesTerminologyExampleSlide 11Another ExampleSlide 13Algorithm/Running Time AnalysisRunning Time•Why do we need to analyze the running time of a program?•Option 1: Run the program and time it–Why is this option bad?–What can we do about it?Pseudo-Code•Used to specify algorithms•Part English, part codeAlgorithm (arrayMax(A, n))curMax = A[0]for i=1 i<n i++ if curMax < A[i] curMax = A[i]return curMaxMath Review•Summation – ∑ •Sum of n consecutive digits = n(n+1)/2Counting OperationsAlgorithm (arrayMax(A, n))curMax = A[0]//1 for i=1 i<n i++ //n//1 or 2if curMax < A[i] curMax = A[i]return curMax //1•Best case – n+2 •Worst case – 2n + 2 •Average case – hard to analyzeAsymptotic Notation•2n + 2•n=5 -> 12•n=100 -> 202•n=1,000,000 -> 2,000,002•Running time grows proportionally to n•What happens as n gets large?Big-Oh•f(n) is O(g(n)) if there is a real constant c>0 and an integer constant n0>=1 such that f(n) <= cg(n) for every integer n>=n0•2n+2 is O(n) n0>=1 c=3Examples•87n4 + 7n•3nlogn + 12logn•4n4 + 7n3lognTerminology•Logarithmic – O(logn)•Linear – O(n)•Linearithmic – O(nlogn)•Quadratic – O(n2)•Polynomial – O(nk) k>=1•Exponential – O(an) a>1Example•Find maximum number in nxn matrix•Algorithm:6 4 … 212 3 … 9… … … …5 8 … 10n-1n-10Example•What is the big-oh running time of this algorithm?Algorithm:Input: A, ncurMax = A[0][0]for i=0 i<n i++for j=0 j<n j++if curMax < A[i][j]curMax = A[i][j]return curMaxAnother Example•Determine how many elements of array 1 match elements of array 2•Algorithm?2 4 … 6n-106 8 … 3n-10Another ExampleAlgorithm:Input: A, B, nfor i=0 i<n i++for j=0 j<n j++if A[i] == A[j]matches++break•What is the running time of the algorithm?2 4 … 6n-106 8 …
View Full Document
Unlocking...