Algorithm Analysis | Reliable Papers

16/11/20181BIG OWeek 61LESSON OBJECTIVES Data Structure ,Algorithm and Complexity Definitions Example of Basic Operations Average, Best, and Worst Cases. Simple Complexity Analysis Examples.216/11/20182DEFINITIONS Data Structure: is the way in which the data of the programare stored. Algorithm: is a well defined sequence of computationalsteps to solve a problem. It is often accepts a set of valuesas input & produces a set of values as output. Algorithm Analysis: is the number of steps or instructionsand memory locations needed to perform a certainproblem for any input of a particular size3MOTIVATIONS FOR COMPLEXITYANALYSIS There are often many different algorithms which can be used to solvethe same problem. Thus, it makes sense to develop techniques thatallow us to:o compare different algorithms with respect to their “efficiency”o choose the most efficient algorithm for the problem The efficiency of any algorithmic solution to a problem is a measureof the:o Time efficiency: the time it takes to execute.o Space efficiency: the space (primary or secondary memory) it uses. We will focus on an algorithm’s efficiency with respect to time.416/11/20183MACHINE INDEPENDENCE The evaluation of efficiency should be as machineindependent as possible. It is not useful to measure how fast the algorithm runs asthis depends on which particular computer, OS,programming language, compiler, and kind of inputs areused in testing Instead,o we count the number of basic operations the algorithm performs.o we calculate how this number depends on the size of the input. A basic operation is an operation which takes a constantamount of time to execute. Hence, the efficiency of an algorithm is the number ofbasic operations it performs. This number is a function ofthe input size n.5EXAMPLE 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 onthe 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 twobasic operations. Note: To simplify complexity analysis we will not consider memoryaccess (fetch or store) operations.616/11/20184BEST, AVERAGE, AND WORST CASE COMPLEXITIES We are usually interested in the worst case complexity: what are themost operations that might be performed for a given problem size. Wewill not discuss the other cases — best and average case. 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)7BEST, AVERAGE, AND WORST CASE COMPLEXITIES 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 MethodWorst CaseAverage CaseSelection sortN2n2Inserstion sortn2n2Merge sortn log nn log nQuick sortn2n log n 16/11/20185SIMPLE COMPLEXITY ANALYSIS: LOOPS (WITH 2 operations. The for loop actually comprises an assignment (i = 0) => 1 operation a test (i < n) => n + 1 operations an increment (i++) => 2 n operations the loop body that has three assignments, two multiplications, and anaddition => 6 n operationsThus the total number of basic operations is 6 * n + 2 * n + (n + 1) + 3= 9n + 4double x, y;x = 2.5 ; y = 3.0;for(int i = 0; i < n; i++){a[i] = x * y;x = 2.5 * x;y = y + a[i];}1016/11/20186SIMPLE COMPLEXITY ANALYSIS: EXAMPLES Suppose n is a multiple of 2. Determine the number of basic operationsperformed by of the method myMethod(): Solution: The number of iterations of the loop:for(int i = 1; i < n; i = i * 2)sum = sum + i + helper(i);is log2n (Explanation will be given in class)Hence the number of basic operations is:1 + 1 + (1 + log2n) + log2n[2 + 4 + 1 + 1 + (n + 1) + n[2 + 2] + 1] + 1= 3 + log2n + log2n[10 + 5n] + 1= 5 n log2n + 11 log2n + 4static int myMethod(int n){int sum = 0;for(int i = 1; i < n; i = i * 2)sum = sum + i + helper(i);return sum;}static int helper(int n){int sum = 0;for(int i = 1; i