DOC PREVIEW
USF CS 112 - Algorithm/Running Time Analysis

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 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 13 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 13 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 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

USF CS 112 - Algorithm/Running Time Analysis

Documents in this Course
Structs

Structs

4 pages

Trees

Trees

25 pages

Strings

Strings

27 pages

Queues

Queues

3 pages

Trees

Trees

24 pages

Arrays

Arrays

5 pages

ArrayList

ArrayList

24 pages

Stacks

Stacks

2 pages

Stacks

Stacks

8 pages

Trees

Trees

24 pages

Stacks

Stacks

8 pages

Queues

Queues

16 pages

Queues

Queues

17 pages

Queues

Queues

17 pages

Load more
Download Algorithm/Running Time Analysis
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 Algorithm/Running Time Analysis 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 Algorithm/Running Time Analysis 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?