Critical Section of AlgorithmHeart of algorithmDominates overall execution timeCharacteristicsOperation central to functioning of programContained inside deeply nested loopsExecuted as often as any other part of algorithmSourcesLoopsRecursionCritical Section Example 1Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.B4.CCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒C ⇒⇒⇒⇒Time ⇒⇒⇒⇒Critical Section Example 1Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.B4.CCode executionA ⇒⇒⇒⇒onceB ⇒⇒⇒⇒n timesC ⇒⇒⇒⇒onceTime ⇒⇒⇒⇒ 1 + n + 1 = O(n)critical sectionCritical Section Example 2Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.B4.for (int j = 0; j < n; j++)5.C6.DCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒Time ⇒⇒⇒⇒C ⇒⇒⇒⇒D ⇒⇒⇒⇒Critical Section Example 2Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.B4.for (int j = 0; j < n; j++)5.C6.DCode executionA ⇒⇒⇒⇒onceB ⇒⇒⇒⇒n timesTime ⇒⇒⇒⇒ 1 + n + n2+ 1 = O(n2)critical sectionC ⇒⇒⇒⇒n2timesD ⇒⇒⇒⇒onceCritical Section Example 3Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.for (int j = i+1; j < n; j++)4.BCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒Time ⇒⇒⇒⇒Critical Section Example 3Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.for (int j = i+1; j < n; j++)4.BCode executionA ⇒⇒⇒⇒onceB ⇒⇒⇒⇒½ n (n-1) timesTime ⇒⇒⇒⇒ 1 + ½ n2= O(n2)critical sectionCritical Section Example 4Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.for (int j = 0; j < 10000; j++)4.BCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒Time ⇒⇒⇒⇒Critical Section Example 4Code (for input size n)1.A2.for (int i = 0; i < n; i++)3.for (int j = 0; j < 10000; j++)4.BCode executionA ⇒⇒⇒⇒onceB ⇒⇒⇒⇒10000 n timesTime ⇒⇒⇒⇒ 1 + 10000 n = O(n)critical sectionCritical Section Example 5Code (for input size n)1.for (int i = 0; i < n; i++)2.for (int j = 0; j < n; j++)3.A4.for (int i = 0; i < n; i++)5.for (int j = 0; j < n; j++)6.BCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒Time ⇒⇒⇒⇒Critical Section Example 5Code (for input size n)1.for (int i = 0; i < n; i++)2.for (int j = 0; j < n; j++)3.A4.for (int i = 0; i < n; i++)5.for (int j = 0; j < n; j++)6.BCode executionA ⇒⇒⇒⇒n2 timesB ⇒⇒⇒⇒n2 timesTime ⇒⇒⇒⇒ n2 +n2= O(n2)critical sectionsCritical Section Example 6Code (for input size n)1.i = 12.while (i < n)3.A4.i = 2 ×××× i5.BCode executionA ⇒⇒⇒⇒B ⇒⇒⇒⇒Time ⇒⇒⇒⇒Critical Section Example 6Code (for input size n)1.i = 12.while (i < n)3.A4.i = 2 ×××× i5.BCode executionA ⇒⇒⇒⇒log(n) timesB ⇒⇒⇒⇒1 timesTime ⇒⇒⇒⇒ log(n) + 1 = O( log(n) )critical sectionCritical Section Example 7Code (for input size n)1.DoWork (int n)2.if (n == 1)3.A4.else5.DoWork(n/2)6.DoWork(n/2)Code executionA ⇒⇒⇒⇒DoWork(n/2) ⇒⇒⇒⇒Time(1) ⇒⇒⇒⇒ Time(n) =Critical Section Example 7Code (for input size n)1.DoWork (int n)2.if (n == 1)3.A4.else5.DoWork(n/2)6.DoWork(n/2)Code executionA ⇒⇒⇒⇒1 timesDoWork(n/2) ⇒⇒⇒⇒2 timesTime(1) ⇒⇒⇒⇒ 1 Time(n) = 2 ×××× Time(n/2) + 1critical sectionsAsymptotic Complexity Categories Complexity Name ExampleO(1) Constant Array accessO(log(n)) Logarithmic Binary searchO(n) Linear Largest elementO(n log(n)) N log N Optimal sortO(n2) Quadratic 2D Matrix additionO(n3) Cubic 2D Matrix multiplyO(nk) Polynomial Linear programmingO(kn) Exponential Integer programmingFrom smallest to largest For size n, constant k > 1Comparing ComplexityCompare two algorithmsf(n), g(n)Determine which increases at faster rateAs problem size n increasesCan compare ratioIf ∞∞∞∞, f() is largerIf 0, g() is largerIf constant, then same complexitylimn→→→→∞∞∞∞f(n)g(n)Complexity Comparison Exampleslog(n) vs. n½1.001nvs. n1000limn→→→→∞∞∞∞f(n)g(n)limn→→→→∞∞∞∞log(n)n½0limn→→→→∞∞∞∞f(n)g(n)limn→→→→∞∞∞∞1.001nn1000??Not clear, use L’Hopital’s RuleL’Hopital’s RuleIf ratio is indeterminate0 / 0 or ∞∞∞∞ / ∞∞∞∞Ratio of derivatives computes same valueCan simplify ratio by repeatedly taking derivatives of numerator & denominatorlimn→→→→∞∞∞∞f(n)g(n)limn→→→→∞∞∞∞f'(n)g'(n)=Using L’Hopital’s Rule1.001nvs. n1000limn→→→→∞∞∞∞f(n)g(n)limn→→→→∞∞∞∞1.001nn1000limn→→→→∞∞∞∞1.001nln(1.001)1000 n999limn→→→→∞∞∞∞1.001nln(1.001)ln(1.001)1000××××999 n998∞∞∞∞…Additional Complexity MeasuresUpper boundBig-O ⇒⇒⇒⇒ΟΟΟΟ(…)Represents upper bound on # stepsLower boundBig-Omega ⇒⇒⇒⇒ΩΩΩΩ(…)Represents lower bound on # stepsCombined boundBig-Theta⇒⇒⇒⇒ΘΘΘΘ(…)Represents combined upper/lower bound on # stepsBest possible asymptotic solution2D Matrix Multiplication ExampleProblemC = A * BLower boundΩΩΩΩ(n2) Required to examine 2D matrixUpper boundsO(n3) Basic algorithmO(n2.807) Strassen’s algorithm (1969)O(n2.376) Coppersmith & Winograd (1987)Improvements still possible (open problem)Since upper & lower bounds do not
View Full Document
Unlocking...