logging in or signing up Data structures chapter 2(1) ali48 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 185 Category: Science & Tech.. License: All Rights Reserved Like it (0) Dislike it (0) Added: October 02, 2010 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: janniceyumul (13 month(s) ago) pls allow me to download the slides they are very interesting.thanks Saving..... Post Reply Close Saving..... Edit Comment Close By: ali48 (20 month(s) ago) yes you can Saving..... Post Reply Close Saving..... Edit Comment Close By: sachink66 (20 month(s) ago) The slides are very interesting. Can I download them? Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Slide 1: Copyright © Kashif Javed Algorithm Analysis 2-1 Chapter 2 Algorithm Analysis EE 232 Data StructuresSession-05 , Spring-07 Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-2 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-3 Chapter 2: Algorithm Analysis Our goals: we shall learn How to estimate the time required for a program How to reduce the running time of a program The results of careless use of recursion Very efficient algorithms to raise a number to a power and to compute the greatest common divisor of two numbers Lets Recall : Copyright © Kashif Javed Algorithm Analysis 2-4 Lets Recall What is an Algorithm? a clearly specified set of simple instructions to be followed to solve a problem Takes a set of values, as input and produces a value, or set of values, as output What are Data structures? Methods of organizing data Program = algorithms + data structures Lets Recallā¦ : Copyright © Kashif Javed Algorithm Analysis 2-5 Lets Recallā¦ Why should we analyse an algorithm? Writing a working program is not good enough! The program may be inefficient If the program is run on a large data set, then the running time becomes an issue Recall the selection problem Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-6 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Mathematical Background : Copyright © Kashif Javed Algorithm Analysis 2-7 Mathematical Background We need a theoretical framework upon which we can compare algorithms The idea is to establish a relative order among different algorithms, in terms of their relative rates of growth (of the running time) The rates of growth are expressed as functions, which are generally in terms of the number of inputs n e.g. a running time function can be expressed as T(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-8 Mathematical Backgroundā¦ Such functions describe the utilization of some precious resource (e.g. time or space) as the size of the problem increases We can determine the exact running time of an algorithm, however for large inputs, the multiplicative constants and lower-order terms are dominated by the effects of the input size itself Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-9 Mathematical Backgroundā¦ *Consider the two functions f(n) = n2 and g(n) = n2 ā 3n + 2 Around n = 0, they look very different *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-10 Mathematical Backgroundā¦ *If we look at a slightly larger range fromn = [0, 10], we begin to note that they are more similar: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-11 Mathematical Backgroundā¦ *Extending the range to n = [0, 100], the similarity increases: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-12 Mathematical Backgroundā¦ *And on the range n = [0, 1000], they are (relatively) indistinguishable: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-13 Mathematical Backgroundā¦ *They are different absolutely, for example, f(1000) = 1 000 000 g(1000) = 997 002 however, the relative difference is very small and this difference goes to zero as n ā ā The justification for the pair of polynomials being similar is that, both have the same leading term: n2 *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-14 Mathematical Backgroundā¦ We can throw away the lower-order terms and ignore the leading coefficients of the highest term as the problem size grows really, really large Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-15 Mathematical Backgroundā¦ Asymptotic Analysis simplifies the analysis of running time by getting rid of ādetailsā, which may be affected by specific implementation and hardware like āroundingā: 1,000,001 » 1,000,000 3n2 » n2 Asymptotic Efficiency how the running time of an algorithm increases with the size of the input in the limit, as the size of input increases without bound Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-16 Mathematical Backgroundā¦ Asymptotic Notation The ābig-Ohā O-Notation f(n) 1= O(g(n)) , if there exists positive constants c and n0, such that f(n) £ cg(n) for all n ā„ n0 f(n) and g(n) are functions over non-negative integers The growth rate of f(n) is less than or equal to that of g(n) 1: means set membership i.e. f(n) Š O(g(n)) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-17 Mathematical Backgroundā¦ g(n) is an upper bound on f(n) O-notation provides an asymptotic upper bound on a function Used for worst-case analysis Examples If f(n) = 2n2 , then f(n) = O(n4) , f(n) = O(n3) and f(n) = O(n2) are all technically correct but the last answer is the best Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-18 Mathematical Backgroundā¦ The ābig-Omegaā W -Notation f(n) = W(g(n)) , if there exists positive constants c and n0, such that cg(n) £ f(n) for all n ³ n0 The growth rate of f(n) is greater than or equal to that of g(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-19 Mathematical Backgroundā¦ Wānotation provides an asymptotic lower bound on a function Used to describe best-case running times Examples n3 grows faster than n2 , so we can say that n3 = W(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-20 Mathematical Backgroundā¦ The ābig-Thetaā Q-Notation f(n) = Q(g(n)) if there exists positive constants c1, c2, and n0, such that c1g(n) £ f(n) £ c2g(n) for all n ³ n0 for all values of n to the right of n0 , the values of f(n) lies at or above c1g(n) and at or below c2g(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-21 Mathematical Backgroundā¦ f(n) = Q(g(n)) if and only if f(n) = O(g(n)) and f(n) = W(g(n)) The growth rate of f(n) equals the growth rate of g(n) g(n) is an asymptotically tight bound for f(n) Examples ½n2 ā 3n = Q(n2) 6n3 ā Q(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-22 Mathematical Backgroundā¦ The "Little-Oh" o-notation f(n) = o(g(n)) if f(n) = O(g(n)) and f(n) ā Q (g(n)) The growth rate of f(n) is less than the growth rate of g(n) This is different from Big-Oh, because Big-Oh allows the possibility that growth rates are the same Examples The bound 2n2 = O(n2) is asymptotically tight but the bound 2n = O(n2) is not 2n = o(n2) , but 2n2 ā o(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-23 Mathematical Backgroundā¦ Rule 1 If T1(n) = O(f(n)) and T2(n) = O(g(n)) , then T1(n) + T2(n) = max( O(f(n)), O(g(n)) ) , T1(n) * T2(n) = O( f(n) * g(n) ) Rule2 If T(n) is a polynomial of degree k, then T(n) = Q(nk) e.g. f(n) = an2 + bn +c ļ f(n) = Q(n2) Rule3 logk n = O(n) for any constant k, indicating logarithms grow very slowly Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-24 Mathematical Backgroundā¦ Asymptotic notation in equations and inequalities Asymptotic notation can be used within mathematical formulas 2n2 + 3n + 1 = 2n2 + Q(n) means that 2n2 + 3n + 1 = 2n2 + f(n) where f(n) is some function in the set Q(n) When the asymptotic notation stands alone on the right-hand side of an equation ( or inequality), as in n = O(n2) , we define the equal sign to mean set membership: n Š O(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-25 Mathematical Backgroundā¦ Typical growth rates Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-26 Mathematical Backgroundā¦ A Hierarchy of Growth Rates log n < log2n < logkn < n < n log n < n2 < n3 < 2n < 3n < n! Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-27 Mathematical Backgroundā¦ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-28 Mathematical Backgroundā¦ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-29 Mathematical Backgroundā¦ We can always determine the relative growth rates of two functions f(n) and g(n) by computing using Lā Hopitalās rule if necessary If the limit is 0 ļ f(n) = o(g(n)) ļ If the limit is c ā 0 ļ f(n) = Q(g(n)) If the limit is ā ļ g(n) = o(f(n)) f(n) becomes insignificant relative to g(n) as n approaches infinity Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-30 Mathematical Backgroundā¦ LāHopitalās Rule where f ā(n) and gā(n) are the derivates of f(n) and g(n) respectively Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-31 Mathematical Backgroundā¦ Example Let f(n) = 25n2 + n and g(n) = n2 Then So 25n2 + n = Ī(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-32 Mathematical Backgroundā¦ Example Let f(n) = n logn and g(n) = n1.5 Then Answer: n logn = o(n1.5) Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-33 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Model : Copyright © Kashif Javed Algorithm Analysis 2-34 Model In order to analyze algorithms in our formal framework, we need a model of computation Instructions are executed sequentially ļ Instructions are executed one after another, with no concurrent operations ļ Not parallel computers Simple instructions such as addition, multiplication, comparison and assignment and each instruction is executed exactly in one time unit ļ not a realistic assumption Modelā¦ : Copyright © Kashif Javed Algorithm Analysis 2-35 Modelā¦ Assume infinite memory ļ never worry about page faults Although the compiler and computer affect algorithms , we will not model them here Why do we use a model? simple easier to prove things for the model than the real machine We can estimate the algorithm behavior irrespective of the hardware/software Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-36 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations What to analyze : Copyright © Kashif Javed Algorithm Analysis 2-37 What to analyze We only analyse correct algorithms An algorithm is correct If, for every input instance, it halts with the correct output Incorrect algorithms Might not halt at all on some input instances Might halt with other than the desired answer What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-38 What to analyzeā¦ Analysing an algorithm Predicting the resources that the algorithm requires Resources include Memory (space complexity) Computational time (time complexity) What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-39 What to analyzeā¦ Factors affecting the running time of an algorithm computerās architecture compilerās design algorithm used input to the algorithm typically, the input size (number of items in the input) is the main consideration e.g. sorting problem ļ the number of items to be sorted i = j-1 ; if c is the cost and it executes for n times, so total = c*n ; c is dependent upon computerās clock and compiler What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-40 What to analyzeā¦ So we want to evaluate an algorithm as the size of the problem becomes large An algorithm that takes linear time grows more slowly than one that is quadratic, and A quadratic algorithm grows more slowly than an exponential Each of these characterizations --- linear, quadratic, and so on --- identifies a class of functions with similar growth behavior What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-41 What to analyzeā¦ Best-case running time if there is a permutation of input data that minimizes ārun time efficiencyā, then that minimum is the best-case run time efficiency Worst-case running time if there is a permutation of input data that maximizes the ārun time efficiencyā, then that maximum is the worst-case run time efficiency We use worst-case running time for analysing algorithms as this provides a bound for all input What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-42 What to analyzeā¦ Best/Worst/Average Case* For a specific size of input n, investigate running times for different input instances: 1n 2n 3n 4n 5n 6n *http://www.cs.aau.dk/~simas/ad01/index.html What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-43 What to analyzeā¦ Best/Worst/Average Case* For inputs of all sizes: *http://www.cs.aau.dk/~simas/ad01/index.html Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-44 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Running Time Calculations : Copyright © Kashif Javed Algorithm Analysis 2-45 Running Time Calculations To simplify the analysis We adopt the convention that there are no particular units of time and thus, we can throw away the leading constants We will also throw away low-order terms, so we compute the Big-Oh running time that provides an upper bound We should never underestimate the running time of a program Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-46 Running Time Calculationsā¦ A Simple Example int sum (int N) { int i, PartialSum; PartialSum = 0; for ( i = 1; i <= N; i++) PartialSum += i * i * i; return PartialSum; } Computing the Time Units --------------------------------- no time for declarations 1 for the assignment 1 assignment, N+1 tests, and N increments 4 units for an assignment, an addition, and two multiplications per loop 1 for the return statement ------------------------------------------------------- T(N) = 1+(1+N+1+N)+4N+1 = 6N+4 = O(N) Analysis becomes too complex for larger programs ā there are ways to simplify this Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-47 Running Time Calculationsā¦ A Simpler Analysis int sum (int N) { int i, PartialSum; PartialSum = 0; for ( i = 1; i <= N; i++) PartialSum += i * i * i; return PartialSum; } Computing the Time Units --------------------------------- insignificant compared with the for loop N loops O(1) statement per execution, so no need to count whether it is two, three or four units insignificant compared with the for loop -------------------------------------------------------- T(N) = N = O(N) The Big-Oh is the same Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-48 Running Time Calculationsā¦ General Rules Rule 1 ā for loops The running time of a for loop is at most the running time of the statements inside the for loop times the number of iterations The T(N) of above example is O(N) for ( i = 0; i < N; i++) sum += i; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-49 Running Time Calculationsā¦ Rule 2 ā nested for loops analyze these inside out The total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the for loops The T(N) of above example is O(N2) for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) k++; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-50 Running Time Calculationsā¦ Rule 3 ā consecutive statements These just add (which means that the maximum is the one that counts) The T(N) of above example is O(N) + O(N2) = O(N2) for ( i = 0; i < N; i++) A[ i ] = 0; for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) A[ i ] += A[ j ] + i +j; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-51 Running Time Calculationsā¦ Rule 4 ā if/else For the fragment: if (condition) s1 else s2 The running time is never more than the running time of the test plus the larger of the running times of s1 and s2 The T(N) of above example is O(N2) if (condition == 1) for (i = 0; i < N; i++) A[ i ] = 0; else for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) A[ i ] += A[ j ] + i +j; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-52 Running Time Calculationsā¦ Basic strategy analyse from the inside (or deepest part) first and work outwards If there are function calls, these must be analysed first This even works for recursive functions Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-53 Running Time Calculationsā¦ Recursive Functions Let T(N) be the running time for Factorial(N) ļ Factorial(N-1) requires T(N-1) time units long int Factorial (int N) { /*1*/ if (N <= 1) /*2*/ return 1; else /*3*/ return N * Factorial(N-1); } Computing the time units ---------------------------------- N = 0 and N = 1, running time is constant which is the time to do the test and return N ā„ 2, running time is a constant work at line 1 + work at line 3 work at line 3 is one multiplication and one function call ------------------------------------------------ T(0) = T(1) = 1, T(N) = T(N-1) + 2 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-54 Running Time Calculationsā¦ A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs ļ§ we can replace asymptotic notations with a representative from itās equivalent class replace Q(1) with 1, and if we had Q(n) we could replace it with n recurrence relation Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-55 Running Time Calculationsā¦ we substitute the recurrence relation continually on the R.H.S. Main equation ļ T(N) = T(N-1) +1 Substitute N-1 in the main equation ļ T(N-1) = T(N-2) +1 From the main equation we have ļ T(N) = T(N-2) +2 Substitute N-2 in the main equation ļ T(N-2) = T(N-3) +1 From the main equation we have ļ T(N) = T(N-3) +3 ļ T(N) = T(N-k) + k ; If k = N ā 1 then ļ T(N) = N = O(N) This function will be called recursively N times and is O(N) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-56 Running Time Calculationsā¦ Careless use of recursion Let T(N) be the running time for Fib(N) ļ Fib(N-1) requires T(N-1) time units ļ Fib(N-2) requires T(N-2) time units long int Fib (int N) { /*1*/ if (N <= 1) /*2*/ return 1; else /*3*/ return Fib(N-1)+Fib(N-2); } Computing the time units ---------------------------------- N = 0 and N = 1, running time is constant which is the time to do the test and return N ā„ 2, running time is a constant work at line 1 + work at line 3 work at line 3, is one addition and two function calls ---------------------------------------------------- T(0) = T(1) =1; T(N) = T(N-1) + T(N-2) +2 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-57 Running Time Calculationsā¦ Careless use of recursionā¦ thus for N ā„ 2 , running time of Fib(N) is T(N) = T(N-1) + T(N-2) + 2 since Fib(N) = Fib(N-1) + Fib(N-2) , we can show T(N) ā„ Fib(N) with the help of induction we can also show with the help of induction that for N > 4 , Fib(N) ā„ (3/2)N thus the running time of the program grows exponentially huge amount of redundant work But where? Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-58 Running Time Calculationsā¦ Maximum Subsequence Sum problem Given integers A1, A2,ā¦,AN , find the maximum value of For convenience, the maximum subsequence sum is 0 if all the integers are negative Example -2, 11, -4, 13, -5, -2 Answer: 20 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-59 Running Time Calculationsā¦ Algorithm 1 Exhaustively tries all the possibilities 1st loop is of size N 2nd loop is of size N ā i 3rd loop is of size jā i+ 1 The running time is O(N3) Precise analysis int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, i, j, k; /* 1*/ MaxSum = 0; /* 2*/ for( i = 0; i < N; i++ ) /* 3*/ for( j = i; j < N; j++ ) { /* 4*/ ThisSum = 0; /* 5*/ for( k = i; k <= j; k++ ) /* 6*/ ThisSum += A[ k ]; /* 7*/ if( ThisSum > MaxSum ) /* 8*/ MaxSum = ThisSum; } /* 9*/ return MaxSum; } How to avoid cubic running time? Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-60 Running Time Calculationsā¦ Algorithm 2 The running time is O(N2) Precise analysis int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, i, j; /* 1*/ MaxSum = 0; /* 2*/ for( i = 0; i < N; i++ ) { /* 3*/ ThisSum = 0; /* 4*/ for( j = i; j < N; j++ ) { /* 5*/ ThisSum += A[ j ]; /* 6*/ if( ThisSum > MaxSum ) /* 7*/ MaxSum = ThisSum; } } /* 8*/ return MaxSum; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-61 Running Time Calculationsā¦ Algorithm 3 This algorithm uses a divide-and-conquer strategy divide ļ split the problem into two roughly equal subproblems, which are then solved recursively conquer ļ patching together the two solutions of the subproblems, and possibly doing a small amount of additional work, to arrive at a solution for the whole problem Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-62 Running Time Calculationsā¦ maximum subsequence sum for left half is 6 maximum subsequence sum for right half is 8 maximum sum in the left half that includes the last element in the left half is 4 (A1-A4) and maximum sum in the right half that includes the first element in the right half is 7 (A5-A7 ) Thus the maximum sum that spans both halves and goes through the middle is 4 + 7 = 11 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-63 Running Time Calculationsā¦ Algorithm 3ā¦ maximum subsequence sum can be in one of the three places entirely in the left half of the input, entirely in the right half of the input it crosses the middle and is in both halves The first two cases can be solved recursively The last case can be obtained by finding largest sum in the left half that includes its last element and the largest sum in the right half that includes its first element Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-64 Running Time Calculationsā¦ Home assignment: Go through the source code Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-65 Running Time Calculationsā¦ Algorithm 3ā¦ Let T(N) be the time to solve a maximum subsequence sum problem of size N If N =1, program takes constant time T(1) = 1 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-66 Running Time Calculationsā¦ Algorithm 3ā¦ Recurrence equation Replace O(N) with N Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-67 Running Time Calculationsā¦ Algorithm 4 The running time is O(N) int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, j; /* 1*/ ThisSum = MaxSum = 0; /* 2*/ for( j = 0; j < N; j++ ) { /* 3*/ ThisSum += A[ j ]; /* 4*/ if( ThisSum > MaxSum ) /* 5*/ MaxSum = ThisSum; /* 6*/ else if( ThisSum < 0 ) /* 7*/ ThisSum = 0; } /* 8*/ return MaxSum; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-68 Running Time Calculationsā¦ Logarithms in the running time General rule An algorithm is O(logN) if it takes a constant O(1) time to cut the problem size by a fraction ( which is usually ½ ) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-69 Running Time Calculationsā¦ Binary 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 Algorithm1 Scan through the list from left to right Running time is linear Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-70 Running Time Calculationsā¦ Algorithm 2 Check if X is the middle element If X is smaller than the middle element, we apply the same strategy to the sorted sub array to left of middle element Likewise, if X is larger than the middle element, we look to the right half int BinarySearch( const ElementType A[ ], ElementType X, int N ){ int Low, Mid, High; /* 1*/ Low = 0; High = N - 1; /* 2*/ while( Low <= High ){ /* 3*/ Mid = ( Low + High ) / 2; /* 4*/ if( A[ Mid ] < X ) /* 5*/ Low = Mid + 1; else /* 6*/ if( A[ Mid ] > X ) /* 7*/ High = Mid - 1; else /* 8*/ return Mid; } /* 9*/ return NotFound; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-71 Running Time Calculationsā¦ Running time All the work done inside the loop takes O(1) per iteration , so lets determine the number of times around the loop The loop starts with High ā Low = N-1 and finishes with High ā Low ā„ -1 Every time through the loop the value High ā Low must be at least halved from its previous value Thus the number of times around the loop is at most ļ Running time is O(log N) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-72 Running Time Calculationsā¦ Euclidās Algorithm The greatest common divisor (Gcd) of two integers is the largest integer that divides both e.g. Gcd(50,15) = 5 Euclidās algorithm depends on result that if M = Nq + r, then gcd(M,N) = gcd(N,r) The algorithm works by continually computing remainders until 0 is reached The last nonzero remainder is the answer Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-73 Running Time Calculationsā¦ Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-74 Running Time Calculationsā¦ Running time The entire running time of the algorithm depends on determining how long the sequence of remainders is Though the remainder does not decrease by a constant factor in one iteration, but after two, it is at most the half of its original value Running time is O(logN) unsigned int Gcd( unsigned int M, unsigned int N ) { unsigned int Rem; /* 1*/ while( N > 0 ) { /* 2*/ Rem = M % N; /* 3*/ M = N; /* 4*/ N = Rem; } /* 5*/ return M; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-75 Running Time Calculationsā¦ Exponentiation Raising an integer to a power (which is also an integer) Number of multiplications can be used as the measurement of running time XN uses N-1 multiplications The following recursive algorithm does better If N is even, we have XN = XN/2 * XN/2 , and if N is odd, we have XN = X(N-1)/2 * X(N-1)/2 * X Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-76 Running Time Calculationsā¦ Example To calculate 3N = 314, we donāt need to do 13 multiplications (3*3*3*3*3*3*3*3*3*3*3*3*3*3) Instead we notice that 314 = (32)7 But 9^7 can be computed as 9*96 = 9*(92)3 But 81^3 can be computed as 81*(812) 812 = 6,561 81 * 6,561 = 531,441 9 * 531,441 = 4,782,969 which is in fact 314 Each time we square the number, we cut N in half Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-77 Running Time Calculationsā¦ long int Pow( long int X, unsigned int N ) { /* 1*/ if( N == 0 ) /* 2*/ return 1; /* 3*/ if( N == 1 ) /* 4*/ return X; /* 5*/ if( IsEven( N ) ) /* 6*/ return Pow( X * X, N / 2 ); else /* 7*/ return Pow( X * X, N / 2 ) * X; } Computing Time Units ------------------------------- Concentrate on the multiplications 1 multiplications and T(N/2) 2 multiplications and T(N/2) ------------------------------------------ T(N) = 2+T(N/2) Exponentiation Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-78 Running Time Calculationsā¦ Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-79 Running Time Calculationsā¦ Checking your analysis Once an analysis has been performed, it is desirable to see if the answer is correct and as good as possible i.e. verify that some program is O(f(N)) Method 1 Code up your program and see if the empirically observed running time matches the running time predicted by the analysis Difficult to differentiate Linear programs from O(NlogN) purely on empirical evidence Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-80 Running Time Calculationsā¦ Checking your analysisā¦ Method 2 Compute the values of T(N)/f(N) for a range of N where T(N) is the empirically observed running time If f(N) is a tight answer for running time, then the computed values converge to a positive constant If f(N) is an overestimate, values converge to zero If f(N) is an underestimate and hence wrong , the values will diverge Algorithm Analysis: Summary : Copyright © Kashif Javed Algorithm Analysis 2-81 Algorithm Analysis: Summary Covered Asymptotic notations Model of computation How to estimate the running time Both Gcd and exponentiation algorithms are used in cryptography You now have: we learnt how to analyse the complexity of programs , though it is not complete and we will learn more in the coming chapters Proof that T(N) >= F(N) : Copyright © Kashif Javed Algorithm Analysis 2-82 Proof that T(N) >= F(N) Proof that F(N) >= (3/2)N : Copyright © Kashif Javed Algorithm Analysis 2-83 Proof that F(N) >= (3/2)N You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Data structures chapter 2(1) ali48 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 185 Category: Science & Tech.. License: All Rights Reserved Like it (0) Dislike it (0) Added: October 02, 2010 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: janniceyumul (13 month(s) ago) pls allow me to download the slides they are very interesting.thanks Saving..... Post Reply Close Saving..... Edit Comment Close By: ali48 (20 month(s) ago) yes you can Saving..... Post Reply Close Saving..... Edit Comment Close By: sachink66 (20 month(s) ago) The slides are very interesting. Can I download them? Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Slide 1: Copyright © Kashif Javed Algorithm Analysis 2-1 Chapter 2 Algorithm Analysis EE 232 Data StructuresSession-05 , Spring-07 Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-2 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-3 Chapter 2: Algorithm Analysis Our goals: we shall learn How to estimate the time required for a program How to reduce the running time of a program The results of careless use of recursion Very efficient algorithms to raise a number to a power and to compute the greatest common divisor of two numbers Lets Recall : Copyright © Kashif Javed Algorithm Analysis 2-4 Lets Recall What is an Algorithm? a clearly specified set of simple instructions to be followed to solve a problem Takes a set of values, as input and produces a value, or set of values, as output What are Data structures? Methods of organizing data Program = algorithms + data structures Lets Recallā¦ : Copyright © Kashif Javed Algorithm Analysis 2-5 Lets Recallā¦ Why should we analyse an algorithm? Writing a working program is not good enough! The program may be inefficient If the program is run on a large data set, then the running time becomes an issue Recall the selection problem Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-6 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Mathematical Background : Copyright © Kashif Javed Algorithm Analysis 2-7 Mathematical Background We need a theoretical framework upon which we can compare algorithms The idea is to establish a relative order among different algorithms, in terms of their relative rates of growth (of the running time) The rates of growth are expressed as functions, which are generally in terms of the number of inputs n e.g. a running time function can be expressed as T(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-8 Mathematical Backgroundā¦ Such functions describe the utilization of some precious resource (e.g. time or space) as the size of the problem increases We can determine the exact running time of an algorithm, however for large inputs, the multiplicative constants and lower-order terms are dominated by the effects of the input size itself Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-9 Mathematical Backgroundā¦ *Consider the two functions f(n) = n2 and g(n) = n2 ā 3n + 2 Around n = 0, they look very different *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-10 Mathematical Backgroundā¦ *If we look at a slightly larger range fromn = [0, 10], we begin to note that they are more similar: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-11 Mathematical Backgroundā¦ *Extending the range to n = [0, 100], the similarity increases: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-12 Mathematical Backgroundā¦ *And on the range n = [0, 1000], they are (relatively) indistinguishable: *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-13 Mathematical Backgroundā¦ *They are different absolutely, for example, f(1000) = 1 000 000 g(1000) = 997 002 however, the relative difference is very small and this difference goes to zero as n ā ā The justification for the pair of polynomials being similar is that, both have the same leading term: n2 *http://www.ece.uwaterloo.ca/~ece250/ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-14 Mathematical Backgroundā¦ We can throw away the lower-order terms and ignore the leading coefficients of the highest term as the problem size grows really, really large Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-15 Mathematical Backgroundā¦ Asymptotic Analysis simplifies the analysis of running time by getting rid of ādetailsā, which may be affected by specific implementation and hardware like āroundingā: 1,000,001 » 1,000,000 3n2 » n2 Asymptotic Efficiency how the running time of an algorithm increases with the size of the input in the limit, as the size of input increases without bound Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-16 Mathematical Backgroundā¦ Asymptotic Notation The ābig-Ohā O-Notation f(n) 1= O(g(n)) , if there exists positive constants c and n0, such that f(n) £ cg(n) for all n ā„ n0 f(n) and g(n) are functions over non-negative integers The growth rate of f(n) is less than or equal to that of g(n) 1: means set membership i.e. f(n) Š O(g(n)) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-17 Mathematical Backgroundā¦ g(n) is an upper bound on f(n) O-notation provides an asymptotic upper bound on a function Used for worst-case analysis Examples If f(n) = 2n2 , then f(n) = O(n4) , f(n) = O(n3) and f(n) = O(n2) are all technically correct but the last answer is the best Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-18 Mathematical Backgroundā¦ The ābig-Omegaā W -Notation f(n) = W(g(n)) , if there exists positive constants c and n0, such that cg(n) £ f(n) for all n ³ n0 The growth rate of f(n) is greater than or equal to that of g(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-19 Mathematical Backgroundā¦ Wānotation provides an asymptotic lower bound on a function Used to describe best-case running times Examples n3 grows faster than n2 , so we can say that n3 = W(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-20 Mathematical Backgroundā¦ The ābig-Thetaā Q-Notation f(n) = Q(g(n)) if there exists positive constants c1, c2, and n0, such that c1g(n) £ f(n) £ c2g(n) for all n ³ n0 for all values of n to the right of n0 , the values of f(n) lies at or above c1g(n) and at or below c2g(n) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-21 Mathematical Backgroundā¦ f(n) = Q(g(n)) if and only if f(n) = O(g(n)) and f(n) = W(g(n)) The growth rate of f(n) equals the growth rate of g(n) g(n) is an asymptotically tight bound for f(n) Examples ½n2 ā 3n = Q(n2) 6n3 ā Q(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-22 Mathematical Backgroundā¦ The "Little-Oh" o-notation f(n) = o(g(n)) if f(n) = O(g(n)) and f(n) ā Q (g(n)) The growth rate of f(n) is less than the growth rate of g(n) This is different from Big-Oh, because Big-Oh allows the possibility that growth rates are the same Examples The bound 2n2 = O(n2) is asymptotically tight but the bound 2n = O(n2) is not 2n = o(n2) , but 2n2 ā o(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-23 Mathematical Backgroundā¦ Rule 1 If T1(n) = O(f(n)) and T2(n) = O(g(n)) , then T1(n) + T2(n) = max( O(f(n)), O(g(n)) ) , T1(n) * T2(n) = O( f(n) * g(n) ) Rule2 If T(n) is a polynomial of degree k, then T(n) = Q(nk) e.g. f(n) = an2 + bn +c ļ f(n) = Q(n2) Rule3 logk n = O(n) for any constant k, indicating logarithms grow very slowly Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-24 Mathematical Backgroundā¦ Asymptotic notation in equations and inequalities Asymptotic notation can be used within mathematical formulas 2n2 + 3n + 1 = 2n2 + Q(n) means that 2n2 + 3n + 1 = 2n2 + f(n) where f(n) is some function in the set Q(n) When the asymptotic notation stands alone on the right-hand side of an equation ( or inequality), as in n = O(n2) , we define the equal sign to mean set membership: n Š O(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-25 Mathematical Backgroundā¦ Typical growth rates Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-26 Mathematical Backgroundā¦ A Hierarchy of Growth Rates log n < log2n < logkn < n < n log n < n2 < n3 < 2n < 3n < n! Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-27 Mathematical Backgroundā¦ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-28 Mathematical Backgroundā¦ Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-29 Mathematical Backgroundā¦ We can always determine the relative growth rates of two functions f(n) and g(n) by computing using Lā Hopitalās rule if necessary If the limit is 0 ļ f(n) = o(g(n)) ļ If the limit is c ā 0 ļ f(n) = Q(g(n)) If the limit is ā ļ g(n) = o(f(n)) f(n) becomes insignificant relative to g(n) as n approaches infinity Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-30 Mathematical Backgroundā¦ LāHopitalās Rule where f ā(n) and gā(n) are the derivates of f(n) and g(n) respectively Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-31 Mathematical Backgroundā¦ Example Let f(n) = 25n2 + n and g(n) = n2 Then So 25n2 + n = Ī(n2) Mathematical Backgroundā¦ : Copyright © Kashif Javed Algorithm Analysis 2-32 Mathematical Backgroundā¦ Example Let f(n) = n logn and g(n) = n1.5 Then Answer: n logn = o(n1.5) Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-33 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Model : Copyright © Kashif Javed Algorithm Analysis 2-34 Model In order to analyze algorithms in our formal framework, we need a model of computation Instructions are executed sequentially ļ Instructions are executed one after another, with no concurrent operations ļ Not parallel computers Simple instructions such as addition, multiplication, comparison and assignment and each instruction is executed exactly in one time unit ļ not a realistic assumption Modelā¦ : Copyright © Kashif Javed Algorithm Analysis 2-35 Modelā¦ Assume infinite memory ļ never worry about page faults Although the compiler and computer affect algorithms , we will not model them here Why do we use a model? simple easier to prove things for the model than the real machine We can estimate the algorithm behavior irrespective of the hardware/software Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-36 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations What to analyze : Copyright © Kashif Javed Algorithm Analysis 2-37 What to analyze We only analyse correct algorithms An algorithm is correct If, for every input instance, it halts with the correct output Incorrect algorithms Might not halt at all on some input instances Might halt with other than the desired answer What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-38 What to analyzeā¦ Analysing an algorithm Predicting the resources that the algorithm requires Resources include Memory (space complexity) Computational time (time complexity) What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-39 What to analyzeā¦ Factors affecting the running time of an algorithm computerās architecture compilerās design algorithm used input to the algorithm typically, the input size (number of items in the input) is the main consideration e.g. sorting problem ļ the number of items to be sorted i = j-1 ; if c is the cost and it executes for n times, so total = c*n ; c is dependent upon computerās clock and compiler What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-40 What to analyzeā¦ So we want to evaluate an algorithm as the size of the problem becomes large An algorithm that takes linear time grows more slowly than one that is quadratic, and A quadratic algorithm grows more slowly than an exponential Each of these characterizations --- linear, quadratic, and so on --- identifies a class of functions with similar growth behavior What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-41 What to analyzeā¦ Best-case running time if there is a permutation of input data that minimizes ārun time efficiencyā, then that minimum is the best-case run time efficiency Worst-case running time if there is a permutation of input data that maximizes the ārun time efficiencyā, then that maximum is the worst-case run time efficiency We use worst-case running time for analysing algorithms as this provides a bound for all input What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-42 What to analyzeā¦ Best/Worst/Average Case* For a specific size of input n, investigate running times for different input instances: 1n 2n 3n 4n 5n 6n *http://www.cs.aau.dk/~simas/ad01/index.html What to analyzeā¦ : Copyright © Kashif Javed Algorithm Analysis 2-43 What to analyzeā¦ Best/Worst/Average Case* For inputs of all sizes: *http://www.cs.aau.dk/~simas/ad01/index.html Chapter 2: Algorithm Analysis : Copyright © Kashif Javed Algorithm Analysis 2-44 Chapter 2: Algorithm Analysis 2.1 Mathematical Background 2.2 Model 2.3 What to Analyze 2.4 Running Time Calculations Running Time Calculations : Copyright © Kashif Javed Algorithm Analysis 2-45 Running Time Calculations To simplify the analysis We adopt the convention that there are no particular units of time and thus, we can throw away the leading constants We will also throw away low-order terms, so we compute the Big-Oh running time that provides an upper bound We should never underestimate the running time of a program Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-46 Running Time Calculationsā¦ A Simple Example int sum (int N) { int i, PartialSum; PartialSum = 0; for ( i = 1; i <= N; i++) PartialSum += i * i * i; return PartialSum; } Computing the Time Units --------------------------------- no time for declarations 1 for the assignment 1 assignment, N+1 tests, and N increments 4 units for an assignment, an addition, and two multiplications per loop 1 for the return statement ------------------------------------------------------- T(N) = 1+(1+N+1+N)+4N+1 = 6N+4 = O(N) Analysis becomes too complex for larger programs ā there are ways to simplify this Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-47 Running Time Calculationsā¦ A Simpler Analysis int sum (int N) { int i, PartialSum; PartialSum = 0; for ( i = 1; i <= N; i++) PartialSum += i * i * i; return PartialSum; } Computing the Time Units --------------------------------- insignificant compared with the for loop N loops O(1) statement per execution, so no need to count whether it is two, three or four units insignificant compared with the for loop -------------------------------------------------------- T(N) = N = O(N) The Big-Oh is the same Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-48 Running Time Calculationsā¦ General Rules Rule 1 ā for loops The running time of a for loop is at most the running time of the statements inside the for loop times the number of iterations The T(N) of above example is O(N) for ( i = 0; i < N; i++) sum += i; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-49 Running Time Calculationsā¦ Rule 2 ā nested for loops analyze these inside out The total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the for loops The T(N) of above example is O(N2) for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) k++; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-50 Running Time Calculationsā¦ Rule 3 ā consecutive statements These just add (which means that the maximum is the one that counts) The T(N) of above example is O(N) + O(N2) = O(N2) for ( i = 0; i < N; i++) A[ i ] = 0; for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) A[ i ] += A[ j ] + i +j; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-51 Running Time Calculationsā¦ Rule 4 ā if/else For the fragment: if (condition) s1 else s2 The running time is never more than the running time of the test plus the larger of the running times of s1 and s2 The T(N) of above example is O(N2) if (condition == 1) for (i = 0; i < N; i++) A[ i ] = 0; else for ( i = 0; i < N; i++) for ( j = 0; j < N; j++) A[ i ] += A[ j ] + i +j; Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-52 Running Time Calculationsā¦ Basic strategy analyse from the inside (or deepest part) first and work outwards If there are function calls, these must be analysed first This even works for recursive functions Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-53 Running Time Calculationsā¦ Recursive Functions Let T(N) be the running time for Factorial(N) ļ Factorial(N-1) requires T(N-1) time units long int Factorial (int N) { /*1*/ if (N <= 1) /*2*/ return 1; else /*3*/ return N * Factorial(N-1); } Computing the time units ---------------------------------- N = 0 and N = 1, running time is constant which is the time to do the test and return N ā„ 2, running time is a constant work at line 1 + work at line 3 work at line 3 is one multiplication and one function call ------------------------------------------------ T(0) = T(1) = 1, T(N) = T(N-1) + 2 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-54 Running Time Calculationsā¦ A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs ļ§ we can replace asymptotic notations with a representative from itās equivalent class replace Q(1) with 1, and if we had Q(n) we could replace it with n recurrence relation Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-55 Running Time Calculationsā¦ we substitute the recurrence relation continually on the R.H.S. Main equation ļ T(N) = T(N-1) +1 Substitute N-1 in the main equation ļ T(N-1) = T(N-2) +1 From the main equation we have ļ T(N) = T(N-2) +2 Substitute N-2 in the main equation ļ T(N-2) = T(N-3) +1 From the main equation we have ļ T(N) = T(N-3) +3 ļ T(N) = T(N-k) + k ; If k = N ā 1 then ļ T(N) = N = O(N) This function will be called recursively N times and is O(N) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-56 Running Time Calculationsā¦ Careless use of recursion Let T(N) be the running time for Fib(N) ļ Fib(N-1) requires T(N-1) time units ļ Fib(N-2) requires T(N-2) time units long int Fib (int N) { /*1*/ if (N <= 1) /*2*/ return 1; else /*3*/ return Fib(N-1)+Fib(N-2); } Computing the time units ---------------------------------- N = 0 and N = 1, running time is constant which is the time to do the test and return N ā„ 2, running time is a constant work at line 1 + work at line 3 work at line 3, is one addition and two function calls ---------------------------------------------------- T(0) = T(1) =1; T(N) = T(N-1) + T(N-2) +2 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-57 Running Time Calculationsā¦ Careless use of recursionā¦ thus for N ā„ 2 , running time of Fib(N) is T(N) = T(N-1) + T(N-2) + 2 since Fib(N) = Fib(N-1) + Fib(N-2) , we can show T(N) ā„ Fib(N) with the help of induction we can also show with the help of induction that for N > 4 , Fib(N) ā„ (3/2)N thus the running time of the program grows exponentially huge amount of redundant work But where? Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-58 Running Time Calculationsā¦ Maximum Subsequence Sum problem Given integers A1, A2,ā¦,AN , find the maximum value of For convenience, the maximum subsequence sum is 0 if all the integers are negative Example -2, 11, -4, 13, -5, -2 Answer: 20 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-59 Running Time Calculationsā¦ Algorithm 1 Exhaustively tries all the possibilities 1st loop is of size N 2nd loop is of size N ā i 3rd loop is of size jā i+ 1 The running time is O(N3) Precise analysis int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, i, j, k; /* 1*/ MaxSum = 0; /* 2*/ for( i = 0; i < N; i++ ) /* 3*/ for( j = i; j < N; j++ ) { /* 4*/ ThisSum = 0; /* 5*/ for( k = i; k <= j; k++ ) /* 6*/ ThisSum += A[ k ]; /* 7*/ if( ThisSum > MaxSum ) /* 8*/ MaxSum = ThisSum; } /* 9*/ return MaxSum; } How to avoid cubic running time? Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-60 Running Time Calculationsā¦ Algorithm 2 The running time is O(N2) Precise analysis int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, i, j; /* 1*/ MaxSum = 0; /* 2*/ for( i = 0; i < N; i++ ) { /* 3*/ ThisSum = 0; /* 4*/ for( j = i; j < N; j++ ) { /* 5*/ ThisSum += A[ j ]; /* 6*/ if( ThisSum > MaxSum ) /* 7*/ MaxSum = ThisSum; } } /* 8*/ return MaxSum; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-61 Running Time Calculationsā¦ Algorithm 3 This algorithm uses a divide-and-conquer strategy divide ļ split the problem into two roughly equal subproblems, which are then solved recursively conquer ļ patching together the two solutions of the subproblems, and possibly doing a small amount of additional work, to arrive at a solution for the whole problem Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-62 Running Time Calculationsā¦ maximum subsequence sum for left half is 6 maximum subsequence sum for right half is 8 maximum sum in the left half that includes the last element in the left half is 4 (A1-A4) and maximum sum in the right half that includes the first element in the right half is 7 (A5-A7 ) Thus the maximum sum that spans both halves and goes through the middle is 4 + 7 = 11 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-63 Running Time Calculationsā¦ Algorithm 3ā¦ maximum subsequence sum can be in one of the three places entirely in the left half of the input, entirely in the right half of the input it crosses the middle and is in both halves The first two cases can be solved recursively The last case can be obtained by finding largest sum in the left half that includes its last element and the largest sum in the right half that includes its first element Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-64 Running Time Calculationsā¦ Home assignment: Go through the source code Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-65 Running Time Calculationsā¦ Algorithm 3ā¦ Let T(N) be the time to solve a maximum subsequence sum problem of size N If N =1, program takes constant time T(1) = 1 Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-66 Running Time Calculationsā¦ Algorithm 3ā¦ Recurrence equation Replace O(N) with N Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-67 Running Time Calculationsā¦ Algorithm 4 The running time is O(N) int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, j; /* 1*/ ThisSum = MaxSum = 0; /* 2*/ for( j = 0; j < N; j++ ) { /* 3*/ ThisSum += A[ j ]; /* 4*/ if( ThisSum > MaxSum ) /* 5*/ MaxSum = ThisSum; /* 6*/ else if( ThisSum < 0 ) /* 7*/ ThisSum = 0; } /* 8*/ return MaxSum; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-68 Running Time Calculationsā¦ Logarithms in the running time General rule An algorithm is O(logN) if it takes a constant O(1) time to cut the problem size by a fraction ( which is usually ½ ) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-69 Running Time Calculationsā¦ Binary 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 Algorithm1 Scan through the list from left to right Running time is linear Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-70 Running Time Calculationsā¦ Algorithm 2 Check if X is the middle element If X is smaller than the middle element, we apply the same strategy to the sorted sub array to left of middle element Likewise, if X is larger than the middle element, we look to the right half int BinarySearch( const ElementType A[ ], ElementType X, int N ){ int Low, Mid, High; /* 1*/ Low = 0; High = N - 1; /* 2*/ while( Low <= High ){ /* 3*/ Mid = ( Low + High ) / 2; /* 4*/ if( A[ Mid ] < X ) /* 5*/ Low = Mid + 1; else /* 6*/ if( A[ Mid ] > X ) /* 7*/ High = Mid - 1; else /* 8*/ return Mid; } /* 9*/ return NotFound; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-71 Running Time Calculationsā¦ Running time All the work done inside the loop takes O(1) per iteration , so lets determine the number of times around the loop The loop starts with High ā Low = N-1 and finishes with High ā Low ā„ -1 Every time through the loop the value High ā Low must be at least halved from its previous value Thus the number of times around the loop is at most ļ Running time is O(log N) Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-72 Running Time Calculationsā¦ Euclidās Algorithm The greatest common divisor (Gcd) of two integers is the largest integer that divides both e.g. Gcd(50,15) = 5 Euclidās algorithm depends on result that if M = Nq + r, then gcd(M,N) = gcd(N,r) The algorithm works by continually computing remainders until 0 is reached The last nonzero remainder is the answer Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-73 Running Time Calculationsā¦ Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-74 Running Time Calculationsā¦ Running time The entire running time of the algorithm depends on determining how long the sequence of remainders is Though the remainder does not decrease by a constant factor in one iteration, but after two, it is at most the half of its original value Running time is O(logN) unsigned int Gcd( unsigned int M, unsigned int N ) { unsigned int Rem; /* 1*/ while( N > 0 ) { /* 2*/ Rem = M % N; /* 3*/ M = N; /* 4*/ N = Rem; } /* 5*/ return M; } Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-75 Running Time Calculationsā¦ Exponentiation Raising an integer to a power (which is also an integer) Number of multiplications can be used as the measurement of running time XN uses N-1 multiplications The following recursive algorithm does better If N is even, we have XN = XN/2 * XN/2 , and if N is odd, we have XN = X(N-1)/2 * X(N-1)/2 * X Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-76 Running Time Calculationsā¦ Example To calculate 3N = 314, we donāt need to do 13 multiplications (3*3*3*3*3*3*3*3*3*3*3*3*3*3) Instead we notice that 314 = (32)7 But 9^7 can be computed as 9*96 = 9*(92)3 But 81^3 can be computed as 81*(812) 812 = 6,561 81 * 6,561 = 531,441 9 * 531,441 = 4,782,969 which is in fact 314 Each time we square the number, we cut N in half Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-77 Running Time Calculationsā¦ long int Pow( long int X, unsigned int N ) { /* 1*/ if( N == 0 ) /* 2*/ return 1; /* 3*/ if( N == 1 ) /* 4*/ return X; /* 5*/ if( IsEven( N ) ) /* 6*/ return Pow( X * X, N / 2 ); else /* 7*/ return Pow( X * X, N / 2 ) * X; } Computing Time Units ------------------------------- Concentrate on the multiplications 1 multiplications and T(N/2) 2 multiplications and T(N/2) ------------------------------------------ T(N) = 2+T(N/2) Exponentiation Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-78 Running Time Calculationsā¦ Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-79 Running Time Calculationsā¦ Checking your analysis Once an analysis has been performed, it is desirable to see if the answer is correct and as good as possible i.e. verify that some program is O(f(N)) Method 1 Code up your program and see if the empirically observed running time matches the running time predicted by the analysis Difficult to differentiate Linear programs from O(NlogN) purely on empirical evidence Running Time Calculationsā¦ : Copyright © Kashif Javed Algorithm Analysis 2-80 Running Time Calculationsā¦ Checking your analysisā¦ Method 2 Compute the values of T(N)/f(N) for a range of N where T(N) is the empirically observed running time If f(N) is a tight answer for running time, then the computed values converge to a positive constant If f(N) is an overestimate, values converge to zero If f(N) is an underestimate and hence wrong , the values will diverge Algorithm Analysis: Summary : Copyright © Kashif Javed Algorithm Analysis 2-81 Algorithm Analysis: Summary Covered Asymptotic notations Model of computation How to estimate the running time Both Gcd and exponentiation algorithms are used in cryptography You now have: we learnt how to analyse the complexity of programs , though it is not complete and we will learn more in the coming chapters Proof that T(N) >= F(N) : Copyright © Kashif Javed Algorithm Analysis 2-82 Proof that T(N) >= F(N) Proof that F(N) >= (3/2)N : Copyright © Kashif Javed Algorithm Analysis 2-83 Proof that F(N) >= (3/2)N