3.3 Complexity of AlgorithmsSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Complexity ClassesSlide 17Slide 183.3 Complexity of Algorithms•Linear Search Algorithm Determine if 3 is in the following lists A= { 1 4 8 -1 2 } B= { 3 4 8 6 5 } C= { 1 2 4 9 10 11 12 14 19 10 -11 0 } D= { 1 3 2 4 } For each list ( problem ), how much time will the algorithm take to finish the problem ?3.3 Complexity of Algorithms•Recall that the linear search algorithm go through the list from the beginning of the list until reaching the number ( 3 ) or the end of list. •Procedure linear search (x: integer a1, a2, . . . , an ) i=1; while ( i <= n and x =/= ai ) i := i+1 if i <= n, then location := i else location := 03.3 Complexity of AlgorithmsA= { 1 4 8 -1 2 } ( exist at the end of the list)B= { 3 4 8 6 5 } (exist at the beginning of the list)C= { 1 2 4 9 10 11 12 14 19 10 -11 0 }D= { 1 3 2 4 } (exit after comparing two elements) List B will finish before lists A, B and C, even though list B is longer than D. List C will take the longest to finish.3.3 Complexity of Algorithms A= { 1 4 8 -1 2 } B= { 3 4 8 6 5 } C= { 1 2 4 9 10 11 12 14 19 10 -11 0 } D= { 1 3 2 4 } Clearly, the time the algorithm takes to finish1. Depends on the size of the problem (list).2. Even for problems of the same size, there are worst-case, best case, and average case.3.3 Complexity of Algorithms1. Time Complexity: Analysis of the time required to solve a problem of a particular size.2. Space Complexity: Analysis of the computer memory required to solve a problem of a particular size.3.3 Complexity of Algorithms•Describe the (worst-case) time complexity of the linear search algorithm.Procedure linear search (x: integer a1, a2, . . . , an ) i=1; while ( i <= n and x =/= ai ) i := i+1 if i <= n, then location := i else location := 0 The time complexity depends on the number of comparisons because they are the basic operations used.So how many comparisons are there if (in the worst-case) you have to go to the end of the list?3.3 Complexity of Algorithms1. At each step of the loop, there are two comparisons.2. Outside the loop, there is one more comparison.Therefore, if the list has n elements, we will have 2 n + 1 comparisons. In our machine, if each comparison takes k seconds (say, k = 0.00001), then for a list of size n, we’d expect that the algorithm to finish in k* (2 n + 1) seconds.This result is linear (degree one) in n. If list A is twice as long as list B, it will take twice as long to finish A than B.The complexity (in this case) is denote as O(n) (big-O of n, we will discuss this next week 3.2).3.3 Complexity of AlgorithmsNote that we will never know the exact time the algorithm will take to finish a given problem (that depends also on the machine you use).The main issue addressed by time complexity analysis is how does the algorithm’s performance scale with the size of the problem.The previous example O(n) shows a linear time complexity.There are other examples, such as O(n2), O( log n)…..If the time complexity is O(log n), you have to square n to double the running time (if you just double n, the difference in running time is almost negligible).3.3 Complexity of Algorithms•How about average complexity?Definition: the average number of operations used to solve the problem over all inputs of a given size. The time depends on where the element is located in the list. So given a list of size n. If x is in the first position in the list, it will take 3 comparisons. If it is in the second position, it will take 5 comparisons ….. So average is ( 3 + 5 + … + (2n+1) )/n = (2 ( 1+2+ … +n) +n)/n = n+2.Again, it depends linearly on n.3.3 Complexity of Algorithms•What is the worst-case complexity of bubble sort ?3.3 Complexity of Algorithms•Example•{ 1 –11 50 6 8 –1} Use Bubble Sort (sort in increasing order}•After first pass•{-11 1 6 8 –1 50} (5 = 6 -1 comparisons) •After Second Pass •{-11 1 6 -1 8 50} (4 = 5 -1 comparisons)• After Third Pass•{-11 1 -1 6 8 50} (3 = 4 - 1 comparisons)•After Fourth Pass•{-11 -1 1 6 8 50} (2 = 3 – 1 comparisons)•After Fifth Pass • {-11 -1 1 6 8 50} (1 = 2 – 1 comparisons)•DoneThis list has 6 elements and there are 5 + 4 + 3 + 2 + 1 comparisons.3.3 Complexity of Algorithms•In general, if the list has n elements, we will have to do (n-1) + (n-2) …. + 2 +1 = (n-1) n / 2 comparisons. Notice that the complexity here depends quadratically (degree-2) in n. So if list A is twice as long as list B, it will take four times longer to process A than B.3.3 Complexity of Algorithms•How about insertion sort?3.3 Complexity of Algorithms•Example•{ 1 –11 50 6 8 –1} Use Insertion Sort (sort in increasing order}•After first pass•{-11 1 50 6 8 -1} ( 1 comparison) •After Second Pass•{-11 1 50 6 8 -1} ( 2 comparisons) • After Third Pass•{--11 1 6 50 8 -1} ( 3 comparisons)•After Fourth Pass•{- 11 1 6 8 50 -1} ( 4 comparisons)•After Fifth Pass • {-11 -1 1 6 8 50} ( 2 comparisons, worst-case 5 comparisons)•Done3.3 Complexity of Algorithms•In general, if the list has n elements, we will have to do 1+ 2+ … + (n-1) + (n-2) = (n-1) n / 2 comparisons (the result here is slightly different from the book). Notice that the complexity here depends quadratically (degree-2) in n. So if list A is twice as long as list B, it will take four times longer to process A than B.Complexity ClassesLinear search algorithm has linear complexity θ ( n ).Bubble sort has quadratic complexity θ ( n2 ). Binary search algorithm has logarithmic complexity θ ( log n ).The big-O and big- θ provide a language of describing the (time) complexity of algorithms.Complexity Classesθ ( 1 ) Constant Complexityθ ( log n) Logarithmic Complexityθ ( n ) Linear Complexityθ ( n log n) n log n Complexityθ ( nb ) Polynomial Complexityθ ( bn ) Exponential Complexityθ ( n! ) Factorial ComplexityFor problems with input of size n, the number of operations required by the algorithms.Complexity ClassesHow do we known if a given type of problems is too difficult to solve with computers?Of course, some problems simply cannot be solved.A problem that is solvable using an algorithm with polynomial worst-case