Input SizeTime and space complexity is generally a function of theinput sizeE.g., sorting, multiplicationHow we characterize input size depends:Sorting:number of input itemsMultiplication: total number of bitsGraph algorithms:number of nodes & edgesCS3381Des&AnalofAlg(2001-2002SemA)CityUnivofHK/Deptof CS/HelenaWong2.AnalysisofAlgorithms-6
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 6 Input Size Time and space complexity is generally a function of the input size E.g., sorting, multiplication How we characterize input size depends: Sorting: number of input items Multiplication: total number of bits Graph algorithms: number of nodes & edges
Insertion Sort46123524613365326356163535246CS3381Des&AnalofAlg(2001-2002SemA)CityUnivofHK/Deptof Cs/Helena Wong2.AnalysisofAlgorithms-7
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 7 Insertion Sort
Insertion SortTo sort A[1..n] in place:Steps:31·Pick element Ali]3.Move Alj-1..1] to36the right until324516properposition for365Ali] is found.j+1..n1CurrentlyCurrentlysorted partunsorted partCS3381Des&AnalofAlg(2001-2002SemA)CityUnivof HK/Deptof Cs/HelenaWong2.AnalysisofAlgorithms-8
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 8 Insertion Sort To sort A[1.n] in place: Steps: • Pick element A[j] • Move A[j-1.1] to the right until proper position for A[j] is found. Currently sorted part Currently unsorted part . j j+1.n
Insertion SortSorts A[1..n] in place2INSERTION-SORT(A)1 for i← 2 to n230245263do key ← A[i]5263A3A Insert A[il into the sorted2345sequence A[1.. j - 1].4i←j-l5while i > 0 and A[i] > key6do A[i + 1] ← A[]7i←i-18A[i + 1] ← keyCS3381Des&AnalofAlg(2001-2002SemA)CityUnivof HK/Deptof Cs/HelenaWong2.AnalysisofAlgorithms-9
CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong 2. Analysis of Algorithms - 9 Insertion Sort