Analyzing Algorithms PDF

Analyzing Algorithms / Asymptotic Behaviour CIS 3490 Joe Sawada and Daniel Gabrić University of Guelph CIS 3490 1 / 17 Algorithm analysis In this course, we wil...

Analyzing Algorithms / Asymptotic Behaviour CIS 3490 Joe Sawada and Daniel Gabrić University of Guelph CIS 3490 1 / 17 Algorithm analysis In this course, we will focus on the running time of an algorithm. In many applications the space is also a factor – though often analyzing the space is straightforward. Running time is an important measure for the purposes of scalability. It is an important consideration in economic and scientific applications, since everyone expects computer applications to run as fast as possible. CIS 3490 2 / 17 Algorithm analysis In this course, we will focus on the running time of an algorithm. In many applications the space is also a factor – though often analyzing the space is straightforward. Running time is an important measure for the purposes of scalability. It is an important consideration in economic and scientific applications, since everyone expects computer applications to run as fast as possible. Consider two algorithms that sort a list of n integers. I Student A: “My algorithm sorts 10,000,000 numbers in 4.2 seconds” I Student B: “My algorithm sorts 10,000,000 numbers in 6.3 seconds” Which is better? CIS 3490 2 / 17 Algorithm analysis In this course, we will focus on the running time of an algorithm. In many applications the space is also a factor – though often analyzing the space is straightforward. Running time is an important measure for the purposes of scalability. It is an important consideration in economic and scientific applications, since everyone expects computer applications to run as fast as possible. Consider two algorithms that sort a list of n integers. I Student A: “My algorithm sorts 10,000,000 numbers in 4.2 seconds” I Student B: “My algorithm sorts 10,000,000 numbers in 6.3 seconds” Which is better? Some considerations: I Hardware differences: processor, memory, compiler, OS,... I Initial inputs (one input list may have already been sorted) I What is the performance like for other input sizes? I For what inputs will the algorithms be used? CIS 3490 2 / 17 Experimental Analysis An experimental analysis will run an algorithm for various input sizes (generally n), and plot against the running time. Limitations: 1. Experiments are only on a limited set of test inputs. 2. Comparing algorithms requires similar environments (OS, programming language, compiler, etc), 3. The algorithms must be implemented and executed to perform an analysis. 10 Time (s) 5 0 0 50 100 Input size (n) CIS 3490 3 / 17 Experimental Analysis 10 Alg A Time (s) Alg B 5 0 0 50 100 Input size (n) Which algorithm is better and why? CIS 3490 4 / 17 Experimental Analysis 10 Alg A Time (s) Alg B 5 0 0 50 100 Input size (n) Which algorithm is better and why? In this course, we are interested in what happens as n gets large. However, for specific applications, it is important to understand the use cases of an algorithm – perhaps it is only ever run on relatively small input sizes. CIS 3490 4 / 17 A Better Framework To get around the limitations with experimental analysis we want a framework that: I Takes into account all possible inputs I Allows us to compare algorithms independently of the hardware and software environment I Can be performed by studying a high level description of the algorithm (no implementation required) This gives rise to asymptotic notation O, Ω, Θ for bounding the running times of algorithms. CIS 3490 5 / 17 Average or Worst Case Analysis An average case analysis of an algorithm is very desirable - but it is hard to measure and requires heavy stats. Best case analysis is generally not useful. In most cases, we are interested in the worst case running time - finding the maximum time needed to run an algorithm for a given input size. CIS 3490 6 / 17 Asymptotic Notation Given that n represents the size of the input, we often use a function f (n) or T (n) to represent the running time of an algorithm. Often f (n) is a complicated expression - we are interested in simplifying it so it is easy to compare with the running times of other algorithms We want to know about the running time of an algorithm as n gets large. CIS 3490 7 / 17 Asymptotic Notation Given that n represents the size of the input, we often use a function f (n) or T (n) to represent the running time of an algorithm. Often f (n) is a complicated expression - we are interested in simplifying it so it is easy to compare with the running times of other algorithms We want to know about the running time of an algorithm as n gets large. Thus we use bounds: I O(g(n)) an asymptotic upper bound on f (n) I Ω(g(n)) an asymptotic lower bound on f (n) I Θ(g(n)) a tight bound on f (n) CIS 3490 7 / 17 Big Oh Most of the time we will be interested in finding the upper bounds on the worst case running time. Definition We say that f (n) is O(g(n)) if there is a constant c > 0 such that f (n) ≤ c · g(n) for every integer n ≥ n0 (as n gets large). Example f (n) = n2 + 5n + 76 CIS 3490 8 / 17 Big Oh Most of the time we will be interested in finding the upper bounds on the worst case running time. Definition We say that f (n) is O(g(n)) if there is a constant c > 0 such that f (n) ≤ c · g(n) for every integer n ≥ n0 (as n gets large). Example f (n) = n2 + 5n + 76 ≤ n2 + 5n2 + 76n2 CIS 3490 8 / 17 Big Oh Most of the time we will be interested in finding the upper bounds on the worst case running time. Definition We say that f (n) is O(g(n)) if there is a constant c > 0 such that f (n) ≤ c · g(n) for every integer n ≥ n0 (as n gets large). Example f (n) = n2 + 5n + 76 ≤ n2 + 5n2 + 76n2 ≤ 82n2 is O(n2 ) CIS 3490 8 / 17 Big Oh Example √ f (n) = n2 + 5n log n + n CIS 3490 9 / 17 Big Oh Example √ f (n) = n2 + 5n log n + n 2 ≤ 7n is O(n2 ) - a tight upper bound CIS 3490 9 / 17 Big Oh Example √ f (n) = n2 + 5n log n + n 2 ≤ 7n is O(n2 ) - a tight upper bound is O(n4 ) - not tight CIS 3490 9 / 17 Big Oh Example √ f (n) = n2 + 5n log n + n 2 ≤ 7n is O(n2 ) - a tight upper bound is O(n4 ) - not tight Applying knowledge about the relative growth of functions: √ f (n) = 3n3 log n + 2n3 log log n + 2n3.5 + 3n2 + 4 n CIS 3490 9 / 17 Big Oh Example √ f (n) = n2 + 5n log n + n 2 ≤ 7n is O(n2 ) - a tight upper bound is O(n4 ) - not tight Applying knowledge about the relative growth of functions: √ f (n) = 3n3 log n + 2n3 log log n + 2n3.5 + 3n2 + 4 n ≤ 14n3.5 - isolate largest term is O(n3.5 ) CIS 3490 9 / 17 Big Omega Finding a tight lower bound on the worst case running time to solve an algorithmic problem is often more difficult. Definition We say that f (n) is Ω(g(n)) if there is a constant c > 0 such that f (n) ≥ c · g(n) for every integer n ≥ n0 (as n gets large). Example f (n) = n2 + 5n + 76 ≥ n2 is Ω(n2 ) CIS 3490 10 / 17 Big Theta When an upper and lower bound are the same, we can give a tight bound. Definition We say that f (n) is Θ(g(n)) if there are constants c1 , c2 > 0 such that c1 · g(n) ≤ f (n) ≤ c2 · g(n) for every integer n ≥ n0 (as n gets large). In other words f (n) is Θ(g(n)) if: 1. f (n) is O(g(n)) and 2. f (n) is Ω(g(n)). CIS 3490 11 / 17 Big Theta When an upper and lower bound are the same, we can give a tight bound. Definition We say that f (n) is Θ(g(n)) if there are constants c1 , c2 > 0 such that c1 · g(n) ≤ f (n) ≤ c2 · g(n) for every integer n ≥ n0 (as n gets large). In other words f (n) is Θ(g(n)) if: 1. f (n) is O(g(n)) and 2. f (n) is Ω(g(n)). A tight bound for f (n) f (n) = n2 + 5n + 76 f (n) = n2 + 5n + 76 ≥ n2 ≤ 82n2 2 is Ω(n ) is O(n2 ) Thus, f (n) is Θ(n2 ). CIS 3490 11 / 17 Big Theta Every algorithm has a trivial lower bound of Ω(1) - constant time. Every algorithm can be given an upper bound as well, as long as it does not run to infinity. But, does every algorithm have a tight Θ bound? CIS 3490 12 / 17 Big Theta Every algorithm has a trivial lower bound of Ω(1) - constant time. Every algorithm can be given an upper bound as well, as long as it does not run to infinity. But, does every algorithm have a tight Θ bound? Consider: n2  if n even f (n) = 1 if n odd But what about g(n) = f (n)? CIS 3490 12 / 17 Growth Rate of Functions From smallest to largest: √ log n, log2 n, n, n, n log n, n2 , n3 , 2n n log n n n log n n3 2n 2 1 2 2 8 4 8 3 8 24 512 256 32 5 32 160 32,768 4,294,967,296 128 7 128 896 2,097,152 3.4x1038 512 9 512 4608 134,217,728 1.3x10154 CIS 3490 13 / 17 The Random Access Machine (RAM) Model Definition Not to be confused with Random access memory, the Random Access Machine is a computational model (RAM-model) that views a computer as a CPU connected to a bank of memory cells such that I each memory cell stores a word and I the CPU can access an arbitrary memory cell with one primitive operation. Primitive operations are viewed to take constant O(1) time: I assignment I calling and returning from a method I basic arithmetic operation (addition, multiplication) I comparisons I array indexing, object referencing CIS 3490 14 / 17 Determining the Running Time To determine the running time of an algorithm, we simply count the number of primitive operations performed. This can become challenging when there are loops and even more difficult if there are recursive calls. In general, if there are no loops or recursive calls, then there will only be a constant number of primitive operations, and thus the running time is O(1) - constant time. Consider the code fragment: for i ← 1 to n do x←x+4 y ←x+3 CIS 3490 15 / 17 Determining the Running Time To determine the running time of an algorithm, we simply count the number of primitive operations performed. This can become challenging when there are loops and even more difficult if there are recursive calls. In general, if there are no loops or recursive calls, then there will only be a constant number of primitive operations, and thus the running time is O(1) - constant time. Consider the code fragment: Count primitives: f (n) = 7n + 2 for i ← 1 to n do x←x+4 y ←x+3 CIS 3490 15 / 17 Determining the Running Time To determine the running time of an algorithm, we simply count the number of primitive operations performed. This can become challenging when there are loops and even more difficult if there are recursive calls. In general, if there are no loops or recursive calls, then there will only be a constant number of primitive operations, and thus the running time is O(1) - constant time. Consider the code fragment: Count primitives: f (n) = 7n + 2 for i ← 1 to n do Easier: The loop is executed n times x←x+4 and each iteration requires O(1) work y ←x+3 I Thus, f (n) = O(n) CIS 3490 15 / 17 Recursive algorithms To analyze recursive algorithms, we require the use of recurrence relations. Every recursive algorithm (and hence recurrence) must have a base case - or stopping condition. T (n) denotes the running time of an algorithm for input n. Find the maximum value in list (array) A = a1 , a2 ,... , an with initial call GetMax(A, n) 1: function GetMax(A, j) 2: if j = 1 then return a1. base case! 3: return Max(aj , GetMax(A, j−1)) Assume Max is a function returning the maximum of two numbers. CIS 3490 16 / 17 Recursive algorithms To analyze recursive algorithms, we require the use of recurrence relations. Every recursive algorithm (and hence recurrence) must have a base case - or stopping condition. T (n) denotes the running time of an algorithm for input n. Find the maximum value in list (array) A = a1 , a2 ,... , an with initial call GetMax(A, n) 1: function GetMax(A, j) 2: if j = 1 then return a1. base case! 3: return Max(aj , GetMax(A, j−1)) Assume Max is a function returning the maximum of two numbers. Analysis: I Base case (n = 1): T (n) = 3 I Recursive case (n > 1): T (n) = T (n − 1) + 7 CIS 3490 16 / 17 Recursive algorithms To analyze recursive algorithms, we require the use of recurrence relations. Every recursive algorithm (and hence recurrence) must have a base case - or stopping condition. T (n) denotes the running time of an algorithm for input n. Find the maximum value in list (array) A = a1 , a2 ,... , an with initial call GetMax(A, n) 1: function GetMax(A, j) 2: if j = 1 then return a1. base case! 3: return Max(aj , GetMax(A, j−1)) Assume Max is a function returning the maximum of two numbers. Analysis: I Base case (n = 1): T (n) = 3 I Recursive case (n > 1): T (n) = T (n − 1) + 7  3 if n = 1 T (n) = T (n − 1) + 7 otherwise CIS 3490 16 / 17 Upper vs Lower bounds on Problems Upper Bound The goal is to find an upper bound on the worst case running time to solve a problem. To show a problem has a bound O(f (n)), we simply have to demonstrate a single algorithm that solves the problem for every input in this time. CIS 3490 17 / 17 Upper vs Lower bounds on Problems Upper Bound The goal is to find an upper bound on the worst case running time to solve a problem. To show a problem has a bound O(f (n)), we simply have to demonstrate a single algorithm that solves the problem for every input in this time. Lower Bound The issue is to prove a lower bound on the performance of any algorithm that solves the problem. Thus, to show a problem has a lower bound of Ω(f (n)), we must prove that EVERY possible algorithm that solves the given problem will require at least that much work. CIS 3490 17 / 17 Upper vs Lower bounds on Problems Upper Bound The goal is to find an upper bound on the worst case running time to solve a problem. To show a problem has a bound O(f (n)), we simply have to demonstrate a single algorithm that solves the problem for every input in this time. Lower Bound The issue is to prove a lower bound on the performance of any algorithm that solves the problem. Thus, to show a problem has a lower bound of Ω(f (n)), we must prove that EVERY possible algorithm that solves the given problem will require at least that much work. So far we have looked at finding upper and lower bounds on functions - the running time for a particular algorithm. CIS 3490 17 / 17