EECE 330 Chapter, Fall 2011

Algorithm Analysis EECE 330 Data Structures & Algorithms Algorithm Efficiency There are often many approaches (algorithms) to solve a problem. How do we choose between them? At the heart of computer program design are two (sometimes conflicting) goals. 1. To design an algorithm that is easy to understand, code, debug. 2. To design an algorithm that makes efficient use of the computer’s resources. Algorithm Efficiency (cont) Goal (1) is the concern of Software Engineering. Goal (2) is the concern of data structures and algorithm analysis. When goal (2) is important, how do we measure an algorithm’s cost? How to Measure Efficiency? 1. Empirical comparison (run programs) 2. Asymptotic Algorithm Analysis Critical resources: For most algorithms, running time depends on “size” of the input. Running time is expressed as T(n) for some function T on input size n. Examples of Growth Rate Example 1. // Find largest value int largest(int array[], int n) { int currlarge = 0; // Largest value seen for (int i=1; i<n; i++) // For each val if (array[currlarge] < array[i]) currlarge = i; // Remember pos return currlarge; // Return largest } Examples (cont) Example 2: Assignment statement. Example 3: sum = 0; for (i=1; i<=n; i++) for (j=1; j<n; j++) sum++; } Growth Rate Graph Best, Worst, Average Cases Not all inputs of a given size take the same time to run. Sequential search for K in an array of n integers: • Begin at first element in array and look at each element in turn until K is found Best case: Worst case: Average case: Which Analysis to Use? While average time appears to be the fairest measure, it may be difficult to determine. When is the worst case time important? Faster Computer or Algorithm? What happens when we buy a computer 10 times faster? • Assume an old machine can run 10,000 basic operations in 1 hour • n: maximum size that can be processed in 10,000 ops with the old machine (n’: with the new machine). Notice how higher growth algorithms improve less!  Effort should be spent on improving algorithms T(n) n n’ Change n’/n 10n 1,000 10,000 n’ = 10n 10 20n 500 5,000 n’ = 10n 10 5n log n 250 1,842 10 n < n’ < 10n 7.37 2n2 70 223 n’ = 10n 3.16 2n 13 16 n’ = n + 3 ~1 Upper Bounds: Big-Oh We state: “This algorithm has an upper bound of f(n) to its growth rate”: Too long of a sentence! Or simply state: “This algorithm is in O(f(n))” Definition: For T(n) a non-negatively valued function, T(n) is in O(f(n)) if there exist two positive constants c and n0 such that T(n)  cf(n) for all n > n0. Usage: The algorithm is in O(n2) in [best, average, worst] case. Meaning: For all data sets big enough (i.e., n>n0), the algorithm always executes in less than cf(n) steps in [on the best- case, average-case, or worst-case inputs]. Big-Oh Notation (continued) Example 1: T(n) = c1n2 + c2n in the average case (c1 and c2  0). Since c1n2 + c2n  c1n2 + c2n2  T(n)  cn2 where c=c1+c2  T(n) is in O(n2). Example 2: Finding value X in an array. T(n) = csn/2 in the average case. For all values of n > 1, csn/2  csn.  T(n) is in O(n). Example 3: T(n) = c.  T(n) is in O(1). A Common Misunderstanding “The best case for my algorithm is n=1 because that is the fastest.” WRONG! Big-Oh refers to a growth rate as n grows to . Best case is defined as which input of size n is cheapest among all inputs of size n. Lower Bound: Big-Omega Definition: For T(n) a non-negatively valued function, T(n) is in (g(n)) if there exist two positive constants c and n0 such that T(n)  cg(n) for all n > n0. Meaning: For all data sets big enough (i.e., n > n0), the algorithm always executes in more than cg(n) steps. Big-Omega Example T(n) = c1n2 + c2n. c1n2 + c2n  c1n2 for all n > 1. T(n) >= cn2 for c = c1 and n0 = 1. Therefore, T(n) is in (n2) by the definition. Theta Notation When big-Oh and  meet, we indicate this by using  (big-Theta) notation. Definition: An algorithm is said to be (h(n)) if it is in O(h(n)) and it is in (h(n)). A Common Misunderstanding Confusing worst case with upper bound. Upper bound refers to a growth rate. Worst case refers to the worst input from among the choices for possible inputs of a given size. Simplifying Rules 1. If T(n) is in O(g(n)) and g(n) is in O(h(n)), then T(n) is in O(h(n)). 2. If T(n) is in O(kg(n)) for any constant k > 0, then T(n) is in O(g(n)). 3. If T1(n) is in O(g1(n)) and T2(n) is in O(g2(n)), then (T1+T2)(n) is in O(max(g1(n), g2(n))). 4. If T1(n) is in O(g1(n)) and T2(n) is in O(g2(n)) then T1(n) T2(n) is in O(g1(n)g2(n)). Assignment Example 1: a = b; Example 2: sum = 0; for (i=1; i<=n; i++) sum += n; Example 3: sum = 0; for (j=1; j<=n; j++) for (i=1; i<=j; i+ +) sum++; for (k=0; k<n; k++) A[k] = k; Example 4: sum1 = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) sum1++; sum2 = 0; for (i=1; i<=n; i++) for (j=1; j<=i; j++) sum2++; Example 5: sum1 = 0; for (k=1; k<=n; k*=2) for (j=1; j<=n; j++) sum1++; sum2 = 0; for (k=1; k<=n; k*=2) for (j=1; j<=k; j++) sum2++; Determine O, , and  for all examples below as they apply. Binary Search To begin with, the array should be sorted Compare search value to middle element in array. If less, search in first half, if greater, search in second half. Repeat this process recursively. How many elements are examined in worst case? Determine O, , and  as they apply (see next two slides). Binary Search // Return position of element in sorted // array of size n with value K. int binary(int array[], int n, int K) { int l = -1; int r = n; // l, r are beyond array bounds while (l+1 != r) { // Stop when l, r meet int i = (l+r)/2; // Check middle if (K < array[i]) r = i; // Left half if (K == array[i]) return i; // Found it if (K > array[i]) l = i; // Right half } return n; // Search value not in array } Other Control Statements while loop: Analyze like a for loop. if statement: Take greater complexity of then/else clauses. switch statement: Take complexity of most expensive case. Function/Method call: Complexity of the Function/Method. Analyzing Problems A problem may be solved by multiple algorithms Upper bound of the problem: Upper bound of best known algorithm. Lower bound of the problem : Lower bound for every possible algorithm. Analyzing Problems: Example Common misunderstanding: No distinction between upper/lower bound when you know the exact running time. Example of imperfect knowledge: Sorting 1. Bubble or insertion sort: O(n2). 2. A better sort (Quicksort, Mergesort, Heapsort, etc.): O(n log n). 3. We prove later that sorting is (n log n). Multiple Parameters Compute the rank ordering for all C pixel values (e.g., 255 possible values) in a picture of P pixels. for (i=0; i<C; i++) // Initialize count count[i] = 0; for (i=0; i<P; i++) // Look at all pixels count[value(i)]++; // Increment count sort(count); // Sort pixel counts If we use P as the measure, then time is (P log P). More accurate is (P + C log C). Counting Sorting Space Bounds Space bounds can also be analyzed with asymptotic complexity analysis.  Time is affected mostly by algorithm design  Space is affected mostly by the data structures used Space/Time Tradeoff Principle One can often reduce time if one is willing to sacrifice space, or vice versa. • Encoding or packing information (less space but slower execution) - Example: zipped files • Table lookup (more space but faster execution) - Example Factorials Disk-based Space/Time Tradeoff Principle: The smaller you make the disk storage requirements, the faster your program will run.