CSCD 326 Data Structures I Algorithm AnalysisAlgorithms and Program DesignAlgorithm AnalysisThe Growth Rate FunctionFinding f(n)Slide 6Slide 7Big - O NotationSlide 9Comparison of Algorithms with Different Time ComplexitiesGraph of Growth Rate FunctionsAlgorithm Time ComplexitiesAlgorithms and AnalysisSearch and Sort Testing ProgramLinear (Sequential) SearchAnalysis of Linear SearchBinary SearchBinary Search (2)Binary Search TraceBinary Search Trace 2Binary Search AnalysisSlide 22Slide 23BubblesortBubblesort TraceBubblesort Trace (2)Bubblesort Trace (3)Bubblesort Trace (4)Bubblesort AnalysisBubblesort Analysis (2)BubbleSort : Analysis (3)Improved BubblesortImproved Bubblesort (2)Improved Bubblesort AnalysisSlide 35Slide 36Slide 37Selection SortSelection Sort : indexOfLargestSelection Sort : TraceSlide 41Selection Sort : AnalysisSelection Sort : Analysis (2)Selection Sort : Analysis (3)Insertion SortInsertion Sort : TraceInsertion Sort : Trace (inner loop)Insertion Sort : AnalysisInsertion Sort : Analysis (2)Slide 50Insertion Sort : Analysis (3)Insertion Sort : Analysis (4)Insertion Sort : Analysis (5)Shell Sort - IntroductionShell Sort -General DescriptionShell Sort -BackgroundShell Sort - exampleShell Sort - example (2)Shell Sort - example (3)Gap Sequences for Shell SortShell Sort - Ideal Gap SequenceShell Sort - Practical Gap SequencesShell Sort - Added Gap SequenceSlide 64Shell Sort - Time ComplexityShellsort - CodeShellSort -Trace (gap = 4)ShellSort -Trace (gap = 2)ShellSort -Trace (gap = 1)1CSCD 326 Data Structures IAlgorithm Analysis2Algorithms and Program DesignIs it enough if an algorithm implementation "just works" ?A working algorithm that is poorly designed could execute slowly and thus make one part of a software system sluggish and unresponsive to users.Thus, a central part of computer science is using tools to compare the execution speed of algorithms.This is usually done before an algorithm is implemented in a programming language.3Algorithm AnalysisMathematical tools and techniques that allow comparison of different solutions to the same problem.These techniques analyze algorithms independently of specific implementations, computers, or data.These techniques do not provide fine details about the speed of a solution but allow determination of whether one solution is much (order of magnitude) slower or faster than another.4The Growth Rate FunctionThe simplest way to analyze an algorithm is to count the operations it performs.This is usually not practical since the number of operations depends on the number of data elements to be handled.So - derive a function of n (the data set size) that describes the number of operations as a function of n.This function f(n) is called the growth rate function of the algorithm.5Finding f(n)for(i = 0 ; i < n ; i++) for(j = 0 ; j < n ; j++) { System.out.println("i: "+i); System.out.println("j: "+j); }Involves analysisof the number of loop iterationsThe outer loop executes:one setup statement -- i = 0 once.one comparison on each of n iterationsone auto-increment n timesone final comparison to end the loopone for statement (the inner for) n times what loop does.so f(n) = 2n + n*inner + 26Finding f(n)for(i = 0 ; i < n ; i++) for(j = 0 ; j < n ; j++) { System.out.println("i: "+i); System.out.println("j: "+j); }The inner loop executes:one setup statement -- j = 0 once.one comparison on each of n iterationsone auto-increment n timesone final comparison to end the looptwo output statements n times.so f(n) = 4n + 27Finding f(n)for(i = 0 ; i < n ; i++) for(j = 0 ; j < n ; j++) { System.out.println("i: "+i); System.out.println("j: "+j); }But the inner loop is done once on each iteration of the outer loop so the final f(n) is:f(n) = 2n +n*(4n + 2) + 2 f(n) = 4n2 + 4n + 28Big - O NotationFull definition of Big-O notation:Let f and g be functions on the non-negative integers.Then f(n) is of order at most g(n) : denoted f(n) = O(g(n))This means that there exists a positive constant C such that:|f(n)| <= C(g(n))for all sufficiently large positive integers n.9Big - O NotationWhat it really means:for f(n) = 4n2 + 4n + 2 - g(n) is the dominant term of the polynomial - n2 in this case and thus,4n2 + 4n + 2 <= C (n2) is true if n >= 1 and C = 10.Note that the definition of Big-O notation only holds true for sufficiently large values of n.So an algorithm whose growth rate function is:f(n) = 4n2 + 4n + 2 is said to have time complexity O(n2).Note that Big-O notation provides only a rough categorization of algorithm speed.10Comparison of Algorithms with Different Time ComplexitiesExecution times assume:1 sec execution time per instructionExactly f(n) instructions will be carried out.n = 104 = 10000log2nExecution Timef(n)nn log2nn2n32n1.32877 * 10-5 sec0.1 sec0.13 sec100 sec — 108 µsec106 sec — 11 days 13:46:40>102992 years11Graph of Growth Rate Functions12Algorithm Time ComplexitiesComplexity NameBig-OO(log n)O(n)O(n log n)O(n2)O(n3)O(2n)LogarithmicLinearLog-LinearQuadraticCubicExponentialO(1)ConstantExampleSwapBinary SearchLinear SearchThe “Good” SortSelection SortMatrix MultiplicationTowers of Hanoi13Algorithms and AnalysisIn the following section we will re-examine some basic searching and sorting algorithms and analyze them.14Search and Sort Testing Programpublic class SortSearchTest { public static void main(String[] args) { Integer[] values = new Integer[10]; values[0] = new Integer(15); values[1] = new Integer(9); values[2] = new Integer(13); values[3] = new Integer(20); values[4] = new Integer(5); values[5] = new Integer(0); values[6] = new Integer(7); values[7] = new Integer(10); values[8] = new Integer(3); values[9] = new Integer(2); printem(values); System.out.println("2 found at: "+ linearSearch(values, new Integer(2))); bubbleSort(values, values.length); printem(values); } public static void printem(Comparable[] anArray){ for(int i = 0; i < anArray.length; i++) { System.out.println("array["+i+"]: "+anArray[i]); } }15Linear (Sequential) Searchpublic static int linearSearch(Comparable[ ] anArray, Comparable target) { int index = 0; while(index < anArray.length) { if (target.compareTo(anArray[index]) == 0 ) return index; index++; } return -1;} The algorithm basically steps through the array until it finds its target element (using target.compareTo()) or it steps through