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
