Critical Section of Algorithm Heart of algorithm Dominates overall execution time Characteristics Operation central to functioning of program Contained inside deeply nested loops Executed as often as any other part of algorithm Sources Loops Recursion Critical Section Example 1 Code for input size n 1 A 2 for int i 0 i n i B 3 4 C Code execution A B C Time Critical Section Example 1 Code for input size n 1 A 2 for int i 0 i n i B 3 4 C Code execution A once B n times C once Time 1 n 1 O n critical section Critical Section Example 2 Code for input size n 1 A 2 for int i 0 i n i B for int j 0 j n j C 3 4 5 6 D Code execution A B Time C D Critical Section Example 2 Code for input size n 1 A 2 for int i 0 i n i B for int j 0 j n j C 3 4 5 6 D Code execution A once B n times C n2 times D once Time 1 n n2 1 O n2 critical section Critical Section Example 3 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j i 1 j n j B Code execution A B Time Critical Section Example 3 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j i 1 j n j B Code execution A once B n n 1 times Time 1 n2 O n2 critical section Critical Section Example 4 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j 0 j 10000 j B Code execution A B Time Critical Section Example 4 Code for input size n 1 A 2 for int i 0 i n i 3 4 for int j 0 j 10000 j B Code execution A once B 10000 n times Time 1 10000 n O n critical section Critical Section Example 5 Code for input size n 1 for int i 0 i n i 2 3 4 5 6 for int j 0 j n j A for int i 0 i n i for int j 0 j n j B Code execution A B Time Critical Section Example 5 Code for input size n 1 for int i 0 i n i 2 3 4 5 6 for int j 0 j n j A for int i 0 i n i for int j 0 j n j B Code execution A n2 times B n2 times Time n2 n2 O n2 critical sections Critical Section Example 6 Code for input size n 1 i 1 2 while i n A i 2 i 3 4 5 B Code execution A B Time Critical Section Example 6 Code for input size n 1 i 1 2 while i n A i 2 i 3 4 5 B Code execution A log n times B 1 times Time log n 1 O log n critical section Critical Section Example 7 Code for input size n 1 DoWork int n 2 3 4 5 6 if n 1 A else DoWork n 2 DoWork n 2 Code execution A DoWork n 2 Time 1 Time n Critical Section Example 7 Code for input size n 1 DoWork int n 2 3 4 5 6 if n 1 A else DoWork n 2 DoWork n 2 critical sections Code execution A 1 times DoWork n 2 2 times Time 1 1 Time n 2 Time n 2 1 Asymptotic Complexity Categories Complexity O 1 O log n O n O n log n O n2 O n3 O nk O kn Name Example Constant Logarithmic Linear N log N Quadratic Cubic Polynomial Exponential Array access Binary search Largest element Optimal sort 2D Matrix addition 2D Matrix multiply Linear programming Integer programming From smallest to largest For size n constant k 1 Comparing Complexity Compare two algorithms f n g n Determine which increases at faster rate As problem size n increases Can compare ratio If f is larger f n lim n g n If 0 g is larger If constant then same complexity Complexity Comparison Examples log n vs n f n lim n g n log n lim n n 0 1 001n vs n1000 f n lim n g n n 1 001 lim n n1000 Not clear use L Hopital s Rule L Hopital s Rule If ratio is indeterminate 0 0 or Ratio of derivatives computes same value f n lim n g n f n lim n g n Can simplify ratio by repeatedly taking derivatives of numerator denominator Using L Hopital s Rule 1 001n vs n1000 f n lim n g n n 1 001 lim n n1000 1 001n ln 1 001 lim 999 1000 n n 1 001n ln 1 001 ln 1 001 lim n 1000 999 n998 Additional Complexity Measures Upper bound Big O Represents upper bound on steps Lower bound Big Omega Represents lower bound on steps Combined bound Big Theta Represents combined upper lower bound on steps Best possible asymptotic solution 2D Matrix Multiplication Example Problem C A B Lower bound n2 Required to examine 2D matrix Upper bounds O n3 O n2 807 O n2 376 Basic algorithm Strassen s algorithm 1969 Coppersmith Winograd 1987 Improvements still possible open problem Since upper lower bounds do not match
View Full Document
Unlocking...