Do an extensive line-by-line analysis of these two algorithms as illustrated in the BigO.pdf on Canvas, and determine the Asymptotic Analysis (Big-0) of each. In each of the links you will note an analysis. You analysis may or may not agree with the websites analysis, which is OK.
Bubble Sort
https://www.geeksforgeeks.org/bubble-sort/
Quick Sort
https://www.geeksforgeeks.org/quick-sort/
PowerPoint Presentation BIG-O ALGORITHM ANALYSIS BigO Asymptotic Analysis • Asymptotic notation is a notation which allow us to express the performance of our algorithms in relation to their input. • Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. • Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space (disk or memory usage) by an algorithm. Logarithm Review 20 = 1 log2 1 = 0 21 = 2 log 2 2 = 1 22 = 4 log 2 4 = 2 23 = 8 log 2 8 = 3 24 = 16 log 2 16 = 4 . . . 2n = x log 2 x = n log 2 40 = ? BigO(1) func Swap(int a, int b) int temp = a; a = b; b = temp BigO(logN) func( number) i = 1 while( i <= number="" )="" i="i" *="" 2="" bigo(n)="" func="" (="" container,="" find="" )="" index="0" while="" (index="">< container.size)="" if="" (vdata[index].data="=" find)="" break="" index++="" if="" (index="">= container.size ) index = -1 return index BigO(N^2) func ( container ) while (passes < container.size)="" for="" (index="1;" index="">< container.size;="" index++)="" if="" (container[index]="">< container[index="" -="" 1])="" swap(container[index],="" container[index="" -="" 1])="" bigo(2^n)="" func="" (number)="" if="" (number=""><= 1)="" return="" number="" return="" func(number="" -="" 2)="" +="" func(number="" -="" 1)="" insertion="" sort="" c++="" void="" insertionsort(int="" arr[],="" int="" n)="" {="" int="" i,="" key,="" j;="" for="" (i="1;" i="">< n;="" i++)="" {="" key="arr[i];" j="i" -="" 1;="" while="" (j="">= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } Insertion Sort Java class InsertionSort { void sort(int arr[]) { int n = arr.length; for (int i = 1; i < n;="" ++i)="" {="" int="" key="arr[i];" int="" j="i" -="" 1;="" while="" (j="">= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } } Insertion Sort Python def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >= 0 and key < arr[j]="" :="" arr[j="" +="" 1]="arr[j]" j="" -="1" arr[j="" +="" 1]="key" algorithm="" analysis="" total="" cost="" bigo(n^2)="" f(n)="5??" +="" 3??="" +="" n="" +="" 5="" the="" term="" 5??="" has="" the="" largest="" growth="" rate="" and="" will="" dominate="" the="" other="" terms="" as="" n="" grows="" sufficiently="" large="" the="" 3??="" and="" n="" terms="" can="" be="" discarded="" 5??="" has="" a="" constant="" of="" 5="" that="" can="" be="" omitted,="" leaving="" f(n)="5??" +="" 3??="" +="" n="" +="" 5="O(??)" simplified="" example="" linear="" search="" def="" search(array,="" num,="" find)="" for="" x="" in="" range="" (0,="" num)="" if="" (array[x]="=" find)="" return="" x="" return="" -1="" end="" binary="" search="" def="" binarysearch="" (array,="" left,="" right,="" find)="" if="" right="">= left mid = l + (right - left) / 2 if array[mid] == find return mid else if array[mid] > find return binarySearch(array, left, mid - 1, find) else return binarySearch(array, mid + 1, right, find) else return -1 end Interpolation search def interpolationSearch(array, num, find) lo = 0 hi = (n - 1) while lo <= hi="" and="" find="">= array[lo] and find <= array[hi]="" if="" lo="=" h="" if="" array[lo]="=" find="" return="" lo="" return="" -1="" pos="lo" +="" int(((float(hi="" -="" lo)="" (="" array[hi]="" -="" array[lo]))="" *="" (="" find="" -="" array[lo])))="" if="" array[pos]="=" x="" return="" pos="" if="" array[pos]="">< x lo = pos + 1 else hi = pos - 1 return -1 end hash table def calculatehash( x, n ) // calculate hash of x (arbitrary) % n return hash end def lookup( array, find ) index = calculatehash( find, array.size ) return array[index] end x="" lo="pos" +="" 1="" else="" hi="pos" -="" 1="" return="" -1="" end="" hash="" table="" def="" calculatehash(="" x,="" n="" )="" calculate="" hash="" of="" x="" (arbitrary)="" %="" n="" return="" hash="" end="" def="" lookup(="" array,="" find="" )="" index="CalculateHash(" find,="" array.size="" )="" return="" array[index]="">