Week Six: Algorithmic Complexity

1. Order of growth

1. 3 ways to go

   

2. Need a better way

   

3. Best, Average, Worst cases

   

4. Orders of Growth

   

5. Types of Orders of Growth

   

2. Big Oh Notation

1. Big Oh

   • worst case
   • rate of growth of program relative to the input size

2. Example

   

3. Complexity Classes Ordered low to high

   

4. Laws

   • law of addition: O(n)+O(n*n) = O(n^2)
   • law of multiplication: O(n)*O(n) = O(n^2)

5. Complexity Classes

6. Exponential Complexity

   • most time-consuming one
   • Recursive:Hanoi tower

   

7. Recursion Complexity

   • fib recursion

     

   • Fib with a dict

     

   • Complexity of Iterative Fib

     

   • Complexity of Recursive Fib

     

8. Complexity of Common Python Functions

   

3. Search Algorithms

1. Linear search

2. Bisection search

   • Sorted List

   • Cutting down the size of the problem in half!!

   • complexity = O(logn)

   • 2 Bisection Search Implementation

     def bisect_search1(L, e):
         if L == []:
             return False
         elif len(L) == 1:
             return L[0] == e
         else:
             half = len(L)//2
             if L[half] > e:
                 return bisect_search1( L[:half], e)
             else:
                 return bisect_search1( L[half:], e)
          
          
          
     def bisect_search2(L, e):
         def bisect_search_helper(L, e, low, high):
             if high == low:
                 return L[low] == e
             mid = (low + high)//2
             if L[mid] == e:
                 return True
             elif L[mid] > e:
                 if low == mid: #nothing left to search
                     return False
                 else:
                     return bisect_search_helper(L, e, low, mid - 1)
             else:
                 return bisect_search_helper(L, e, mid + 1, high)
         if len(L) == 0:
             return False
         else:
             return bisect_search_helper(L, e, 0, len(L) - 1)
     

     

3. sorting

   1. Monkey Sort

      • bogosort also known as permutation sort, stupid sort,slowsort,shotgun sort or monkey sort)
      • a highly ineffective sorting algorithm based on the generate and test paradigm.
      • The function successively generates permutations of its input until it finds one that is sorted.
      • It is not useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms.

   2. Bubble Sort

      • compare consecutive pairs of elements

      • swap elements in pair such that smaller is first

      • when reach end of list, start over again

      • stop when no more swaps have been made

      • def bubble_sort(L):
            swap = False
            while not swap:
                swap = True
                for j in range(1,len(L)):
                    print(L)
                    if L[j] < L[j-1]:
                        temp = L[j]
                        L[j] = L[j-1]
                        L[j-1] = temp
                        swap = False
                
        L = [1, 5, 3, 8, 4, 9, 6, 2]
                                
        

   3. Selection Sort

      • 

      • def Selection_sort(L):
            suffix = 0
            while suffix != len(L):
                for i in range(suffix, len(L)):
                    if L[i] < L[suffix]:
                        temp = L[i]
                        L[i] = L[suffix]
                        L[suffix] = temp
                suffix += 1
                print(L)    
        L = [1, 5, 3, 8, 4, 9, 6, 2]
        

   4. Merge Sort

      • go through two lists

      • compare only smallest elements in each sublist

      • 

      • overall complexity is O(n*log(n))

      • import operator
                
        def mergeSort(L, compare = operator.lt):
            if len(L) < 2:
                return L[:]
            else:
                middle = int(len(L)/2)
                left = mergeSort(L[:middle], compare)
                right = mergeSort(L[middle:], compare)
                print(left)
                print(right)
                return merge(left, right, compare)
                
        def merge(left, right, compare):
            result = []
            i,j = 0, 0
            while i < len(left) and j < len(right):
                if compare(left[i], right[j]):
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            while (i < len(left)):
                result.append(left[i])
                i += 1
            while (j < len(right)):
                result.append(right[j])
                j += 1
            return result
                
        L = [1, 5, 3, 8, 4, 9, 6, 2]
        

   5. Sorting Summary