DOC PREVIEW
FIU COT 5407 - Running Time

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Running TimeExperimental StudiesLimitations of ExperimentsTheoretical AnalysisPseudocodePseudocode DetailsThe Random Access Machine (RAM) ModelPrimitive OperationsSeven Important FunctionsBig-Oh NotationBig-Oh ExampleSlide 12Slide 13Intuition for Asymptotic NotationSlide 15© 2004 Goodrich, Tamassia1Running Time© 2004 Goodrich, Tamassia2Experimental StudiesWrite a program implementing the algorithmRun the program with inputs of varying size and compositionUse a method like System.currentTimeM illis() to get an accurate measure of the actual running timePlot the results© 2004 Goodrich, Tamassia3Limitations of ExperimentsIt is necessary to implement the algorithm, which may be difficultResults may not be indicative of the running time on other inputs not included in the experiment. In order to compare two algorithms, the same hardware and software environments must be used© 2004 Goodrich, Tamassia4Theoretical AnalysisUses a high-level description of the algorithm instead of an implementationCharacterizes running time as a function of the input size, n.Takes into account all possible inputsAllows us to evaluate the speed of an algorithm independent of the hardware/software environment© 2004 Goodrich, Tamassia01/14/19 5PseudocodeHigh-level description of an algorithmMore structured than English proseLess detailed than a programPreferred notation for describing algorithmsHides program design issuesAlgorithm arrayMax(A, n)Input array A of n integersOutput maximum element of AcurrentMax  A[0]for i  1 to n  1 doif A[i]  currentMax thencurrentMax  A[i]return currentMax Example: find max element of an array© 2004 Goodrich, Tamassia6Pseudocode DetailsControl flowif … then … [else …]while … do …repeat … until …for … do …Indentation replaces braces Method declarationAlgorithm method (arg [, arg…])Input …Output …Method callvar.method (arg [, arg…])Return valuereturn expressionExpressionsAssignment(like  in Java)Equality testing(like  in Java)n2Superscripts and other mathematical formatting allowed© 2004 Goodrich, Tamassia01/14/19 7The Random Access Machine (RAM) ModelA CPUA potentially unbounded bank of memory cells, each of which can hold an arbitrary number or character012Memory cells are numbered and accessing any cell in memory takes unit time.© 2004 Goodrich, Tamassia8Primitive OperationsBasic computations performed by an algorithmIdentifiable in pseudocodeLargely independent from the programming languageExact definition not important (we will see why later)Assumed to take a constant amount of time in the RAM modelExamples:Evaluating an expressionAssigning a value to a variableIndexing into an arrayCalling a methodReturning from a method© 2004 Goodrich, Tamassia9Seven Important FunctionsSeven functions that often appear in algorithm analysis:Constant  1Logarithmic  log nLinear  nN-Log-N  n log nQuadratic  n2Cubic  n3Exponential  2nIn a log-log chart, the slope of the line corresponds to the growth rate of the function© 2004 Goodrich, TamassiaAnalysis of Algorithms 10Big-Oh NotationGiven functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constantsc and n0 such thatf(n)  cg(n) for n  n0Example: 2n  10 is O(n)2n  10  cn(c  2) n 10n  10(c  2)Pick c 3 and n0 101101001,00010,0001 10 100 1,000n3n2n+10n© 2004 Goodrich, TamassiaAnalysis of Algorithms 11Big-Oh ExampleExample: the function n2 is not O(n)n2  cnn  cThe above inequality cannot be satisfied since c must be a constant 1101001,00010,000100,0001,000,0001 10 100 1,000nn^2100n10nn© 2004 Goodrich, TamassiaAnalysis of Algorithms 12More Big-Oh Examples7n-27n-2 is O(n)need c > 0 and n0  1 such that 7n-2  c•n for n  n0this is true for c = 7 and n0 = 13n3 + 20n2 + 53n3 + 20n2 + 5 is O(n3)need c > 0 and n0  1 such that 3n3 + 20n2 + 5  c•n3 for n  n0this is true for c = 4 and n0 = 213 log n + 53 log n + 5 is O(log n)need c > 0 and n0  1 such that 3 log n + 5  c•log n for n  n0this is true for c = 8 and n0 = 2© 2004 Goodrich, TamassiaAnalysis of Algorithms 13Relatives of Big-Ohbig-Omegaf(n) is  (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0big-Thetaf(n) is (g(n)) if there are constants c’ > 0 and c’’ > 0 and an integer constant n0  1 such that c’•g(n)  f(n)  c’’•g(n) for n  n0© 2004 Goodrich, TamassiaAnalysis of Algorithms 14Intuition for Asymptotic NotationBig-Ohf(n) is O(g(n)) if f(n) is asymptotically less than or equal to g(n)big-Omegaf(n) is  (g(n)) if f(n) is asymptotically greater than or equal to g(n)big-Thetaf(n) is (g(n)) if f(n) is asymptotically equal to g(n)© 2004 Goodrich, TamassiaAnalysis of Algorithms 15Example Uses of the Relatives of Big-Ohf(n) is (g(n)) if it is (n2) and O(n2). We have already seen the former, for the latter recall that f(n) is O(g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n) < c•g(n) for n  n0 Let c = 5 and n0 = 15n2 is (n2)f(n) is  (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0let c = 1 and n0 = 15n2 is (n)f(n) is  (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0let c = 5 and n0 = 15n2 is


View Full Document

FIU COT 5407 - Running Time

Download Running Time
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Running Time and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Running Time 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?