Algorithms Analysis PDF

Algorithms Analysis Learning Outcomes To be able to:  Carry out simple asymptotic analysis of algorithms  Explain the use of big O, omega, and theta notation to describe the efficiency of an algorithm  Use big O, omega, and theta notation to give asymptotic...

Algorithms Analysis Learning Outcomes To be able to:  Carry out simple asymptotic analysis of algorithms  Explain the use of big O, omega, and theta notation to describe the efficiency of an algorithm  Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms  Determine the time and space complexity of simple algorithms 2 Scope Efficiency goals The concept of algorithm analysis The concept of asymptotic complexity Rules for using big-O Comparing various growth functions How to determine complexity of code structures 3 Introduction An algorithm is a clearly specified set of simple instructions to be followed to solve a problem. Once an algorithm is given for a problem and decided (somehow) to be correct, an important step is to determine how much in the way of resources, such as time or space, the algorithm will require. An algorithm that solves a problem but requires a year is hardly of any use. Likewise, an algorithm that requires hundreds of gigabytes of main memory is not (currently) useful on most machines. To evaluate an algorithm’s efficiency, real-time units such as microseconds and nanoseconds should not be used. Rather, logical units that express a relationship between the size n of a file or an array and the amount of time t required to process the data should be used. 4 Algorithm Efficiency The efficiency of an algorithm is usually expressed in terms of its use of CPU time The analysis of algorithms involves categorizing an algorithm in terms of efficiency An everyday example: washing dishes Suppose washing a dish takes 30 seconds and drying a dish takes an additional 30 seconds Therefore, n dishes require n minutes to wash and dry 5 Computational Complexity The same problem can frequently be solved with different algorithms which differ in efficiency. Computational complexity is a measure of the degree of difficulty of an algorithm and it is used to compare the efficiency of algorithms. Computational complexity indicates how much effort is needed to apply an algorithm or how costly it is. This cost can be measured in a variety of ways. The efficiency of execution of an algorithm depends on the hardware, programming language used, compiler, programming skill, etc. To evaluate an algorithm’s efficiency, logical time units that express a relationship between the size of an input and the amount of time and space required to process the input should be used. 6 Machine Independence The evaluation of efficiency should be as machine independent as possible. It is not useful to measure how fast the algorithm runs as this depends on which particular computer, OS, programming language, compiler, and kind of inputs are used in testing Instead,  we count the number of basic operations the algorithm performs.  we calculate how this number depends on the size of the input. A basic operation is an operation which takes a constant amount of time to execute. Hence, the efficiency of an algorithm is the number of basic operations it performs. This number is a function of the input size n. 7 Example of Basic Operations Arithmetic operations: *, /, %, +, - Assignment statements of simple data types Reading of primitive types Writing of a primitive types Simple conditional tests: if (x < 12)... Method call (Note: the execution time of the method itself may depend on the value of parameter and it may not be constant) A method's return statement Memory Access We consider an operation such as ++ , += , and *= as consisting of two basic operations. Note: To simplify complexity analysis we will not consider memory access (fetch or store) operations. 8 Problem Size For every algorithm we want to analyze, we need to define the size of the problem The dishwashing problem has a size n – number of dishes to be washed/dried For a search algorithm, the size of the problem is the size of the search pool For a sorting algorithm, the size of the program is the number of elements to be sorted The majority of algorithms varies its number of steps based on the size of instance The efficiency of an algorithm is always stated as a function of the problem size  We generally use the variable n to represent the problem size  Typically the size of the input (n) is the main consideration 9 Problem/Input size matters! Some example algorithms and their expected running times based on the input size 10 Growth Functions We must also decide what we are trying to efficiently optimize  time complexity – CPU time  space complexity – memory space CPU time is generally the focus The rates of growth are expressed as functions, which are generally in terms of the number of inputs n A growth function shows the relationship between the size of the problem (n) and the value we hope to optimize (time). This function represents the time complexity or space complexity of the algorithm. 11 Algorithm Complexity Worst Case Complexity:  The function defined by the maximum number of steps taken on any instance of size n Best Case Complexity:  The function defined by the minimum number of steps taken on any instance of size n Average Case Complexity:  The function defined by the average number of steps taken on any instance of size n 12  Algorithm Complexity (cont…) We are usually interested in the worst case complexity: what are the most operations that might be performed for a given problem size. Best case depends on the input Average case is difficult to compute So we usually focus on worst case analysis  Easier to compute  Usually close to the actual running time  Crucial to real-time systems (e.g. air-traffic control) 13 Algorithm Complexity (cont…) Example: Linear Search Complexity Best Case: Item found at the beginning: One comparison Worst Case: Item found at the end: n comparisons Average Case: Item may be found at index 0, or 1, or 2,... or n - 1  Average number of comparisons is: (1 + 2 +... + n) / n = (n + 1) / 2 Worst and Average complexities of common sorting algorithms: Method Worst Case Average Case Selection sort n2 n2 Inserstion sort n2 n2 Merge sort n log n n log n Quick sort n2 n log n 14 Running Time Analysis 15 Asymptotic Complexity It is not typically necessary to know the exact growth function for an algorithm Finding the exact complexity, f(n) = number of basic operations, of an algorithm is difficult We are mainly interested in the asymptotic complexity of an algorithm – the general nature of the algorithm as n increases Asymptotic complexity is based on the dominant term of the growth function – the term that increases most quickly as n increases 16 Asymptotic Complexity (cont…) We approximate f(n) by a function g(n) in a way that does not substantially change the magnitude of f(n). --the function g(n) is sufficiently close to f(n) for large values of the input size n. This "approximate" measure of efficiency is called asymptotic complexity. Thus the asymptotic complexity measure does not give the exact number of operations of an algorithm, but it shows how that number grows with the size of the input. This gives us a measure that will work for different operating systems, compilers and CPUs. Asymptotic bounds are used to estimate the efficiency of algorithms by assessing the amount of time and memory needed to accomplish the task for which the algorithms were designed. 17 Asymptotic Notations Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.  Ο Notation  Ω Notation  θ Notation O(expression) gives an upper bound on the growth rate of a function. It specifically describes the worst-case scenario or the longest amount of time an algorithm can possibly take to complete. Omega(expression) gives a lower bound on the growth rate of a function. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. Theta(expression) consist of all the functions that lie in both O(expression) and Omega(expression). When the upper and lower bounds are the same within a constant factor, we indicate this by using θ(big-Theta) notation. 18 Asymptotic Notations (cont…) Meanings of the various growth functions 19 Big-Oh Notation The most commonly used notation for specifying asymptotic complexity is the big-O notation. The coefficients and the lower order terms become increasingly less relevant as n increases So we say that the algorithm is order n2, which is written O(n2) This is called Big-Oh notation There are various Big-Oh categories Two algorithms in the same category are generally considered to have the same efficiency, but that doesn't mean they have equal growth functions or behave exactly the same for all values of n The Big-O notation, O(g(n)), is used to give an upper bound (worst-case) on a positive runtime function f(n) where n is the input size. 20 Big-O Notation: Definition Big O: T(n) = O(f(n)) if there are positive constants c and N such that T(n) ≤ c f(n) when n ≥ N This says that function T(n) grows at a rate no faster than f(n) ; thus f(n) is an upper bound on T(n). Another way: f(n) is O(g(n))↔ there exist numbers c, N > 0 such that for each n ≥ N f(n) ≤ c g(n) The meaning: f(n) is larger than g(n) only for finite number of n’s; a constant c and a value N can be found so that for every value of n ≥ N: f(n) ≤ c g(n); f(n) does not grow more than a constant factor faster than g(n). 21 Big-O Notation: illustration c g(n) f(n) T(n) = O(f(n)) N n 22 Big-Ω Notation: Definition Big Omega: T(n) = Ω(f(n)) if there are positive constants c and N such that T(n) ≥ c f(n) when n ≥ N This says that function T(n) grows at a rate no slower than f(n) ; thus f(n) is a lower bound on T(n). Another way: f(n) is Ω(g(n))↔ there exist numbers c, N > 0 such that for each n ≥ N f(n) ≥ c g(n) 23 Big-Ω Notation: illustration T(n) = Ω(f(n)) Big-θ Notation The definitions of big-Oh and Ω allow describing the upper bound of an algorithm and the lower bound of an algorithm When the upper and lower bounds are the same within a constant factor, we indicate this by using Θ (big-Theta) notation. An algorithm is said to be Θ(h(n)) if it is in O(h(n)) and it is in Ω(h(n)). 25 Big-θ Notation: Definition Big Theta: T(n) = θ(f(n)) if and only if T(n) = O(f(n)) and T(n) = Ω(f(n)) This says that function T(n) grows at the same rate as f(n). Another way: f(n) is θ(g(n))↔ there exist numbers c1, c2, N > 0 such that for each n ≥ N c1 g(n) ≤ f(n) ≤ c2 g(n) big-Ω notation big-O notation 26 Big-θ Notation: illustration c2 g(n) f(n) c1 g(n) N n Big-Oh Categories Some sample growth functions and their Big-Oh categories: 28 Rules for using big-O For large values of input n, the constants and terms with lower degree of n are ignored. 1. Multiplicative Constants Rule: Ignoring constant factors. O(c f(n)) = O(f(n)), where c is a constant; Example: O(20 n3) = O(n3) 29 Rules for using big-O (cont…) 2. Addition Rule: Ignoring smaller terms.  If O(f(n)) < O(h(n)), then O(f(n) + h(n)) = O(h(n)).  i.e. If T1(n) = O(f(n)) and T2(n) = O(g(n)), then T1(n) + T2(n) = max(O(f(n)), O(g(n))) Example 1: O (n2 log n + n3) = O(n3) O (2000 n3 + 2n! + n800 + 10n + 27n log n + 5) = O(n!) Example 2 (Algorithm A): Step 1: Run algorithm A1 that takes O(n3) time Step 2: Run algorithm A2 that takes O(n2) time TA(n) = TA1(n) + TA2(n) = O(n3) + O(n2) = max (O(n3), O(n2)) = O(n3) 30 Rules for using big-O (cont…) 3. Multiplication Rule:  O(f(n) * h(n)) = O(f(n)) * O(h(n))  i.e. If T1(n) = O(f(n)) and T2(n) = O(g(n)), then T1(n) * T2(n) = O(f(n)) * O(g(n)) Example: O((n3 + 2n2 + 3n log n + 7) (8n2 + 5n + 2)) = O(n5) 31 Rules for using big-O (cont…) 4. If T(n) is a polynomial of degree k, then T(n) = O(nk) Example: T(n) = n8 + 3n5 + 4n2 + 6 = O(n8) logk(n) = O(n) for any constant k 32 Comparing Algorithms Establish a relative order among different algorithms, in terms of their relative rates of growth The rates of growth are expressed as functions, which are generally in terms of the number of inputs n Example: A simple comparison: Let’s assume that you have 3 algorithms to sort a list  f(n) = n log2 n  g(n) = n2  h(n) = n3 Let’s also assume that each step takes 1 microsecond (10-6) n n log n n^2 n^3 10 33.2 100 1000 100 664 10000 1seg 1000 9966 1seg 16min 100000 1.7s 2.8 hours 31.7 years 33 Comparing Growth Functions You might think that faster processors would make efficient algorithms less important A faster CPU helps, but not relative to the dominant term 34 Comparing Growth Functions (cont…) A hierarchy of growth rates: c < log n < log2 n < logk n < n < n log n < n2 < n3 < 2n < 3n < n! < nn 35 Comparing Growth Functions (cont…) As n increases, the various growth functions diverge dramatically: 36 Comparing Growth Functions (cont…) 37 How to determine complexity of code structures NOTE : In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. 38 Analyzing Loop Execution Loops: for, while, and do-while: First determine the order of the body of the loop, then multiply that by the number of times the loop will execute for (int count = 0; count < n; count++) // some sequence of O(1) steps N loop executions times O(1) operations results in a O(n) efficiency Consider the following loop: count = 1; while (count < n) { count *= 2; // some sequence of O(1) steps } The loop is executed log2n times, so the loop is O(log n) 39 Analyzing Loop Execution (cont…) Loops: for, while, and do-while:  Again: complexity is determined by the number of iterations in the loop times multiplied by the complexity of the body of the loop. Examples: for (int i = 0; i < n; i++) sum = sum - i; O(n) for (int i = 0; i < n * n; i++) O(n2) sum = sum + i; i=1; while (i < n) { sum = sum + i; O(log n) i = i*2 } 40  Analyzing Loop Execution (cont…) We start by considering how to count operations in for-loops. First of all, we should know the number of iterations of the loop; say it is x.  Then the loop condition is executed x + 1 times.  Each of the statements in the loop body is executed x times.  The loop-index update statement is executed x times. Example: int sum (int n) Time Units to Compute: { ------------------------ 1 for the assignment int partial_sum = 0; Loop Statement: 1 assignment, n+1 tests, and int i; n increments Loop Body: n loops of 3 units for: for (i = 1; i