DOC PREVIEW
Duke CPS 100E - Analyzing Algorithms

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

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

Unformatted text preview:

Analyzing AlgorithmsWhat is big-Oh about? (preview)More on O-notation, big-OhBig-Oh calculations from codeBig-Oh calculations againAmortization: Expanding ArrayListsSome helpful mathematicsRunning times @ 106 instructions/secCPS 1006.1Analyzing AlgorithmsConsider three solutions to SortByFreqs, also code used in Anagram assignmentSort, then scan looking for changesInsert into Set, then count each unique stringFind unique elements without sorting, sort these, then count each unique stringWe want to discuss trade-offs of these solutionsEase to develop, debug, verifyRuntime efficiencyVocabulary for discussionCPS 1006.2What is big-Oh about? (preview)Intuition: avoid details when they don’t matter, and they don’t matter when input size (N) is big enoughFor polynomials, use only leading term, ignore coefficients y = 3x y = 6x-2 y = 15x + 44 y = x2 y = x2-6x+9 y = 3x2+4xThe first family is O(n), the second is O(n2)Intuition: family of curves, generally the same shapeMore formally: O(f(n)) is an upper-bound, when n is large enough the expression cf(n) is largerIntuition: linear function: double input, double time, quadratic function: double input, quadruple the timeCPS 1006.3More on O-notation, big-OhBig-Oh hides/obscures some empirical analysis, but is good for general description of algorithmAllows us to compare algorithms in the limit•20N hours vs N2 microseconds: which is better?O-notation is an upper-bound, this means that N is O(N), but it is also O(N2); we try to provide tight bounds. Formally:A function g(N) is O(f(N)) if there exist constants c and n such that g(N) < cf(N) for all N > ncf(N)g(N)x = nCPS 1006.4Big-Oh calculations from codeSearch for element in an array:What is complexity of code (using O-notation)?What if array doubles, what happens to time? for(int k=0; k < a.length; k++) { if (a[k].equals(target)) return true; }; return false;Complexity if we call N times on M-element vector?What about best case? Average case? Worst case?CPS 1006.5Big-Oh calculations againAlcohol APT: first string to occur 3 timesWhat is complexity of code (using O-notation)? for(int k=0; k < a.length; k++) { int count = 0; for(int j=0; j <= k; k++) { if (a[j].equals(a[k])) count++; } if (count >= 3) return a[k]; }; return ""; // nothing occurs three timesWhat happens to time if array doubles in size?1 + 2 + 3 + … + n-1, why and what’s O-notation?CPS 1006.6Amortization: Expanding ArrayListsExpand capacity of list when add() calledCalling add N times, doubling capacity as neededWhat if we grow size by one each time?Item # Resizing costCumulative costResizing Cost per itemCapacity After add1 0 0 0 12 2 2 23-4 4 6 1.5 45-8 8 14 1.75 82m+1 - 2m+12 m+12m+2-2 around 2 2m+1CPS 1006.7Some helpful mathematics1 + 2 + 3 + 4 + … + NN(N+1)/2, exactly = N2/2 + N/2 which is O(N2) why?N + N + N + …. + N (total of N times)N*N = N2 which is O(N2) N + N + N + …. + N + … + N + … + N (total of 3N times)3N*N = 3N2 which is O(N2)1 + 2 + 4 + … + 2N 2N+1 – 1 = 2 x 2N – 1 which is O(2N ) Impact of last statement on adding 2N+1 elements to a vector1 + 2 + … + 2N + 2N+1 = 2N+2-1 = 4x2N-1 which is O(2N)CPS 1006.8Running times @ 106 instructions/secN O(log N) O(N) O(N log N)O(N2)100.000003 0.00001 0.000033 0.00011000.000007 0.00010 0.000664 0.10001,0000.000010 0.00100 0.010000 1.010,0000.000013 0.01000 0.132900 1.7 min100,0000.000017 0.10000 1.661000 2.78 hr1,000,0000.000020 1.0 19.9 11.6 day1,000,000,0000.000030 16.7 min 18.3 hr 318


View Full Document

Duke CPS 100E - Analyzing Algorithms

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Analyzing Algorithms
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 Analyzing Algorithms 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 Analyzing Algorithms 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?