Algorithm AnalysisPurposeAlgorithmAlgorithm AnalysisWhat to AnalyzeWhat to AnalyzeExampleWhat to AnalyzeRate of GrowthRate of GrowthRate of GrowthRate of GrowthRate of GrowthRate of GrowthExampleMaxSubSum: Solution 1Slide Number 17Solution 1: AnalysisSolution 1: AnalysisMaxSubSum: Solution 2Slide Number 21Solution 2: AnalysisMaxSubSum: Solution 3MaxSubSum: Solution 3Slide Number 25Slide Number 26Slide Number 27Solution 3: AnalysisMaxSubSum: Solution 4Slide Number 30MaxSubSum Running TimesMaxSubSum Running TimesMaxSubSum Running TimesLogarithmic BehaviorBinary SearchSlide Number 36Euclid’s AlgorithmEuclid’s AlgorithmEuclid’s Algorithm: AnalysisExponentiationExponentiationSummary11Algorithm AnalysisCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State University2Purpose Why bother analyzing code; isn’t getting it to work enough? Estimate time and memory in the average case and worst case Identify bottlenecks, i.e., where to reduce time Speed up critical algorithms3Algorithm Algorithm Well-defined computational procedure for transforming inputs to outputs Problem Specifies the desired input-output relationship Correct algorithm Produces the correct output for every possible input in finite time Solves the problem4Algorithm Analysis Predict resource utilization of an algorithm Running time Memory Dependent on architecture Serial Parallel Quantum5What to Analyze Main focus is on running time Memory/time tradeoff Memory is cheap ($20 per GB) Simple serial computing model Single processor, infinite memoryCray XMT Supercomputer•Up to 64 TB (65,536 GB) shared memory•Up to 8000 processors•128 independent threads per processor•$150M6What to Analyze Running time T(N) N is typically the size of the input Sorting? Multiplying two integers? Multiplying two matrices? Traversing a graph? T(N) measures number of primitive operations performed E.g., addition, multiplication, comparison, assignment7ExampleCostint sum (int n) 0{int partialSum; 0partialSum = 0; 1for (int i = 1; i <= n; i++) 1+(N+1)+NpartialSum += i * i * i; N*(1+1+2)return partialSum; 1}T(N) = 6N+48What to Analyze Worst-case running time Tworst(N) Average-case running time Tavg(N) Tavg(N) <= Tworst(N) Typically analyze worst-case behavior Average case hard to compute Worst-case gives guaranteed upper bound9Rate of Growth Exact expressions for T(N) meaningless and hard to compare Rate of growth Asymptotic behavior of T(N) as N gets big Usually expressed as fastest growing term in T(N), dropping constant coefficients E.g., T(N) = 3N2+ N + 1 Æ Θ(N2)10Rate of Growth T(N) = O(f(N)) if there are positive constants c and n0such that T(N) ≤ cf(N) when N ≥ n0 Asymptotic upper bound “Big-Oh” notation T(N) = Ω(g(N)) if there are positive constants c and n0such that T(N) ≥ cg(N) when N ≥ n0 Asymptotic lower bound “Big-Omega” notation11Rate of Growth T(N) = Θ(h(N)) if and only if T(N) = O(h(N)) and T(N) = Ω(h(N)) Asymptotic tight bound T(N) = o(p(N)) if for all constants c there exists an n0such that T(N) < cp(N) when N>n0 I.e., T(N) = o(p(N)) if T(N) = O(p(N)) and T(N) ≠Θ(p(N)) “Little-oh” notation12Rate of Growth N2= O(N2) = O(N3) = O(2N) N2= Ω(1) = Ω(N) = Ω(N2) N2= Θ(N2) N2= o(N3) 2N2+ 1 = Θ(?) N2+ N = Θ(?)13Rate of Growth Rule 1: If T1(N) = O(f(N)) and T2(N) = O(g(N)), then T1(N) + T2(N) = O(f(N) + g(N)) T1(N) * T2(N) = O(f(N) * g(N)) Rule 2: If T(N) is a polynomial of degree k, then T(N) = Θ(Nk) Rule 3: logk N = O(N) for any constant k14Rate of Growth15Example Maximum subsequence sum problem Given N integers A1, A2, …, AN, find the maximum value (≥ 0) of: Don’t need the actual sequence (i,j) E.g., <1, -4, 4, 2, -3, 5, 8, -2> Æ 16∑=jikkA16MaxSubSum: Solution 1 Compute each possible subsequence independentlyMaxSubSum1 (A)maxSum = 0for i = 1 to Nfor j = i to Nsum = 0for k = i to jsum = sum + A[k]if (sum > maxSum)then maxSum = sumreturn maxSum1718Solution 1: Analysis Three nested for loops, each iterating at most N times Operations inside for loops take constant time Thus, T(N) = ? But, for loops don’t always iterate N times19Solution 1: Analysis More precisely∑∑∑−=−==Θ=101)1()(NiNijjikNT20MaxSubSum: Solution 2 Note that So, no reason to re-compute sum each timeMaxSubSum2 (A)maxSum = 0for i = 1 to Nsum = 0for j = i to Nsum = sum + A[j]if (sum > maxSum)then maxSum = sumreturn maxSum∑∑−==+=1jikkjjikkAAA2122Solution 2: Analysis)()()1()(2101NNTNTNiNijΘ=Θ=∑∑−=−=23MaxSubSum: Solution 3 Recursive, divide and conquer Divide sequence in half A1..centerand A(center+1)..N Recursively compute MaxSubSum of left half Recursively compute MaxSubSum of right half Compute MaxSubSum of sequence constrained to use Acenterand A(center+1) E.g., <1, -4, 4, 2, -3, 5, 8, -2>24MaxSubSum: Solution 3MaxSubSum3 (A, i, j)maxSum = 0if (i = j)then if A[i] > 0then maxSum = A[i]else k = floor((i+j)/2)maxSumLeft = MaxSubSum3(A,i,k)maxSumRight = MaxSubSum3(A,k+1,j)// compute maxSumThruCentermaxSum = Maximum (maxSumLeft,maxSumRight,maxSumThruCenter)return maxSum25262728Solution 3: Analysis T(1) = Θ(1) T(N) = 2T(N/2) + Θ(N) T(N) = Θ(?)29MaxSubSum: Solution 4 Observation Any negative subsequence cannot be a prefix to the maximum sequence Or, a positive, contiguous subsequence is always worth adding T(N) = ?MaxSubSum4 (A)maxSum = 0sum = 0for j = 1 to Nsum = sum + A[j]if (sum > maxSum)then maxSum = sumelse if (sum < 0)then sum = 0return maxSum3031MaxSubSum Running TimesDo not include array read times.38 min26 days32MaxSubSum Running Times33MaxSubSum Running Times34Logarithmic Behavior T(N) = O(log2N) Usually occurs when Problem can be halved in constant time Solutions to sub-problems combined in constant time Examples Binary search Euclid’s algorithm Exponentiation35Binary Search Given an integer X and integers A0,A1,…,AN-1, which are presorted and already in memory, find i such that Ai=X, or return i = -1 if X is not in the input. T(N) = O(log2N) T(N) = Θ(log2N) ?3637Euclid’s Algorithm Compute the greatest common divisor gcd(M,N) between the integers M and N I.e., largest integer that divides both Used in