Algorithms and Data Structures 2 - Algorithm Analysis PDF

Structures 2 Algorithms and Data Structures 2 2 - Algorithm analysis Dr Michele Sevegnani School of Computing Science University of Glasgow [email protected]...

Structures 2 Algorithms and Data Structures 2 2 - Algorithm analysis Dr Michele Sevegnani School of Computing Science University of Glasgow [email protected] Outline Running time Experimental studies vs theoretical analysis Counting primitive operations Growth rate of running time Big-Oh notation ADS 2, 2024 2 Running time Most algorithms transform input 140 objects into output objects 120 The running time of an 100 algorithm typically grows with Running time (s) 80 the input size Average case time is often 60 difficult to determine 40 We mainly focus on the worst- 20 case running time 0 − Easier to analyse 1000 2000 3000 4000 Input size − Crucial to applications such as games, finance and robotics best case average case worst case ADS 2, 2024 3 Experimental studies Write a program implementing 9000 the algorithm 8000 Run the program with inputs of 7000 varying size and composition 6000 Time (ms) Use a method like 5000 System.currentTimeMillis() to 4000 get an accurate measure of the 3000 actual running time 2000 Plot the results 1000 This is also called empirical 0 0 10 20 30 40 50 60 70 80 90 100 algorithmics or performance Input size profiling ADS 2, 2024 4 Experimental studies vs theoretical analysis Limitations of experiments Theory − It is necessary to implement the − Uses a high-level description of the algorithm, which may be difficult algorithm instead of an implementation − Results may not be indicative of the running time on other inputs not − Characterises running time as a included in the experiment function of the input size (n) − In order to compare two algorithms, − Considers all possible inputs the same hardware and software − Allows us to evaluate the speed of an environments must be used algorithm independently of the hardware/software environment ADS 2, 2024 5  Primitive operations Basic computations performed by an algorithm Identifiable in pseudocode Largely independent from the programming language Exact definition not important (we will see why later) Assumed to take a constant amount of time Examples − Expression evaluation − Value assignment to a variable − Array indexing − Method call − Returning from a method ADS 2, 2024 6  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A for i = 1 to n-1 if A[i] > max then max := A[i] {increment counter i} return max ADS 2, 2024 7  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 assignment and for i = 1 to n-1 array indexing if A[i] > max then max := A[i] {increment counter i} return max ADS 2, 2024 8  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n assignment and test if A[i] > max then max := A[i] In general, the loop header is {increment counter i} executed one time more than return max the loop body ADS 2, 2024 9  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n if A[i] > max then 2(n-1) array indexing and test max := A[i] {increment counter i} return max ADS 2, 2024 10  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n if A[i] > max then 2(n-1) max := A[i] 2(n-1) array indexing and {increment counter i} assignment return max Worst case analysis ADS 2, 2024 11  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n if A[i] > max then 2(n-1) max := A[i] 2(n-1) {increment counter i} 2(n-1) assignment and addition return max ADS 2, 2024 12  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n if A[i] > max then 2(n-1) max := A[i] 2(n-1) {increment counter i} 2(n-1) return max 1 return ADS 2, 2024 13  Counting primitive operations By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size Example: find the maximum value in an array A of integers (with indices between 0 and n-1) ARRAY-MAX(A) Operations max := A 2 for i = 1 to n-1 2n if A[i] > max then 2(n-1) max := A[i] 2(n-1) {increment counter i} 2(n-1) return max 1 Total 8n - 3 ADS 2, 2024 14  Estimating running time Algorithm ARRAY-MAX executes 8n  3 primitive operations in the worst case Define − a = time taken by the fastest primitive operation − b = time taken by the slowest primitive operation Let T(n) be worst-case time of ARRAY-MAX The following holds: a (8n  3)  T(n)  b (8n  3) We say the running time T(n) is bounded by two linear functions (i.e. polynomials of degree 1) What is the number of primitive operations in the best case? − How does the input look like? ADS 2, 2024 15  Growth rate of running time Changing the hardware/software environment − Affects T(n) by a constant factor − Does not alter the growth rate of T(n) The linear growth rate of the running time T(n) is an intrinsic property of algorithm ARRAY-MAX − We need to scan the entire array to find the maximum − No assumptions on the input Assume we know the input is always sorted in a descending order − We could get the maximum by simply accessing the first element A, i.e. constant growth rate − We will exploit this fact to define data structures that support finding the maximum more efficiently (e.g. priority queues and heaps) ADS 2, 2024 16 Constant factors The growth rate is not affected by − constant factors − lower-degree terms Examples − 102n + 105 is a linear function − 102n is a linear function − 105n2 + 108n is a quadratic function − … ADS 2, 2024 17 Big-Oh notation Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n)  cg(n) for n  n0 O-notation gives an upper bound for a function to within a constant factor ADS 2, 2024 18 Big-Oh and growth rate The big-Oh notation gives an upper bound on the growth rate of a function The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n) We can use the big-Oh notation to rank functions according to their growth rate f(n) is O(g(n)) g(n) is O(f(n)) g(n) grows more Yes No f(n) grows more No Yes Same growth Yes Yes ADS 2, 2024 19 Asymptotic algorithm analysis When we look at input sizes large enough to make only the growth rate of the running time relevant, we are studying the asymptotic efficiency of algorithms We analyse how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound Big-Oh notation is used to express asymptotic upper bounds ADS 2, 2024 20 Big-Oh rules If f(n) is a polynomial of degree d, then f(n) is O(nd) − Drop lower-order terms − Drop constant factors Use the smallest possible class of functions − Say “2n is O(n)” instead of “2n is O(n2)” Use the simplest expression of the class − Say “3n + 5 is O(n)” instead of “3n + 5 is O(3n)” ADS 2, 2024 21 Some examples 2n + 10 is O(n) Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n)  2n + 10  cn cg(n) for n  n0 n(c  2)  10 n  10/(c  2) Pick c = 3 and n0 = 10 n2 is not O(n) n2  cn nc Since c must be a constant, inequality cannot hold for all n ADS 2, 2024 22 Some examples 7n-2 is O(n) Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n)  7n-2  cn cg(n) for n  n0 Pick c = 8 and n0 = 2 3n3 + 20n2 + 5 is O(n3) 3n3 + 20n2 + 5  cn3 Pick c = 4 and n0 = 21 3 log n + 5 is O(log n) log stands for log2 3 log n + 5  c log n log2 2 = 1 Pick c = 4 and n0 = 32 ADS 2, 2024 23 Big-Oh rules (cont.) If T1(n) = O(f(n)) and T2(n) = O(g(n)) then T1(n) + T2(n) = O(max(f(n),g(n))) Proof − Recall Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n)  cg(n) for n  n0 − There are constants c1 and c2 such that T1(n)  c1f(n) and T2(n)  c2 g(n) for some n sufficiently large − Then T1(n) + T2(n)  c1 f(n) + c2 g(n) − T1(n) + T2(n)  c (f(n) + g(n)), with c = max(c1, c2) − Using a + b ≤ 2 max(a,b) we have T1(n) + T2(n)  2c max(f(n),g(n)) − Hence, T1(n) + T2(n) is O(max(f(n),g(n)) ADS 2, 2024 24 Big-Oh rules (cont.) If T1(n) = O(f(n)) and T2(n) = O(g(n)) then T1(n) T2(n) = O(f(n) g(n)) Proof − Recall Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n)  cg(n) for n  n0 − T1(n)  c1f(n) and T2(n)  c2 g(n) so T1(n) T2(n)  c1c2 f(n) g(n) − Hence, T1(n) T2(n) is O(f(n) g(n)) If T(n) = (log n)k then T(n) = O(n) − True for any value of k − Proof at the end ADS 2, 2024 25  Rules to compute running times Rule 1 – Loops − The running time of a loop is at most the running time of the statements inside the loop (including tests) multiplied by the number of iterations Rule 2 – Nested loops − Should be analysed inside out. Total running time of a statement inside a group of nested loops is running time of statement multiplied by the product of the sizes of all the loops ALG1(n) for i = 0 to n-1 for j = 0 to n-1 O(n3) for k = 0 to n-1 increment x ADS 2, 2024 26  Rules to compute running times Rule 3 – Consecutive statements − These just add (so take the maximum - see slide 24) Rule 4 – If-then-else − Running time is never more than the time of the test (condition) plus the maximum of the running times of the two branches − Similarly for multiple/nested else statements ADS 2, 2024 27 Analysis of INSERTION-SORT Input: an array A of integers (with indices between 0 and n-1) Output: a permutation of the input such that A ≤ A ≤ … ≤ A[n-1] We ignore constants INSERTION-SORT(A) Operations for j = 1 to n-1 n key := A[j] n-1 i := j-1 n-1 while i ≥ 0 and A[i] > key A[i+1] := A[i] -1) i := i-1 -1) A[i+1] := key n-1 ADS 2, 2024 28 Analysis of INSERTION-SORT (cont.) The running time is computed by summing the number of operations − T(n)= n + (n-1) + (n-1) + + -1) + (n-1) Best case: array already sorted − A[i]  key then while loop is never executed: tj = 1 − T(n) = n + (n-1) + (n-1) + (n-1)+ 0 + 0 + (n-1) = O(n) Summation rules Worst case − At every iteration of the while loop we need to shift j elements: tj = j − = = n(n-1)/2 = O(n2) − = n(n-1)/2 – (n – 1) = O(n2) − T(n) = n + (n-1) + (n-1) + O(n2) + O(n2) + O(n2) + (n-1) = O(n2) ADS 2, 2024 29