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 AlgorithmsConsider three solutions to SortByFreqs, also code used in Anagram assignmentSort, then scan looking for changesInsert into Set, then count each unique stringFind unique elements without sorting, sort these, then count each unique stringWe want to discuss trade-offs of these solutionsEase to develop, debug, verifyRuntime efficiencyVocabulary 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 enoughFor polynomials, use only leading term, ignore coefficients y = 3x y = 6x-2 y = 15x + 44 y = x2 y = x2-6x+9 y = 3x2+4xThe first family is O(n), the second is O(n2)Intuition: family of curves, generally the same shapeMore formally: O(f(n)) is an upper-bound, when n is large enough the expression cf(n) is largerIntuition: linear function: double input, double time, quadratic function: double input, quadruple the timeCPS 1006.3More on O-notation, big-OhBig-Oh hides/obscures some empirical analysis, but is good for general description of algorithmAllows 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 codeSearch 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 againAlcohol APT: first string to occur 3 timesWhat 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 timesWhat happens to time if array doubles in size?1 + 2 + 3 + … + n-1, why and what’s O-notation?CPS 1006.6Amortization: Expanding ArrayListsExpand capacity of list when add() calledCalling add N times, doubling capacity as neededWhat 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 mathematics1 + 2 + 3 + 4 + … + NN(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 vector1 + 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