Design and Analysis Of Algorithms
Design and Analysis Of Algorithms CSC 505
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in ComputerScienence
This 24 page Class Notes was uploaded by Jaden Jakubowski on Thursday October 15, 2015. The Class Notes belongs to CSC 505 at North Carolina State University taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/223829/csc-505-north-carolina-state-university in ComputerScienence at North Carolina State University.
Reviews for Design and Analysis Of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/15/15
CSC 505 Spring 2005 Week 5 Lectures page 1 of5 Objectives 0 learn one version of Quicksort 0 learn careful averagecase analysis 0 learn how to deal with histories in recurrences Number of comparisons for sorting algorithms Insertion Sort nQ worst case 0kn if S k items out of order Mergesort 9 n lg n worst case Heapsort 9 n lg n worst case Quicksort nQ worst case n lg n average case Lower Bound 9n lg n worst case and average case Four ways to apply recursion to sorting algorithm decomposition recombination Insertion sort allbutIastlast insert Mergesort split in half merge Selection sort largestallbutlargest concatenate Quicksort m smallerhalfIargerhalf concatenate The rst two do the sorting during recombination the others during decomposition NOTE Heapsort is a variant of selection sort the heap makes the selection of the largest item more efficient Based on notes by Dr Carla DY Savage All rights reserved CSC 505 Spring 2005 Week 5 Lectures page 2 Quicksort Quicksort outline Quicksort Api l l T if p lt T then choose a partition element 1 E Api HT partition Api l l T so that Ai zforap i qil q z Ai21forallq1 i T recursively Quicksort Api l l q 71 and All 1 l l l T The partition procedure function PARTITIONA p T is D returns nal index of pivot 239 H p71J H p z lt7 AT gtlNVAk SzforpgkgiANDAUc gtzforil k jil while j lt T do if AU g I then i lt7 il exchange AU J H J 1 exchange Ai l AT return 239 1 end PARTITION How many comparisons does this take Look at an example a i T j T initial position a A 2 J n 2 J n 2 J n 2 J 13 was swapped with itself swapped the 2 and 4 swapped the l and 4 swapped the 3 and 7 Assumption 1 the pivot7 is equally likely to end up in any one of the n possible array positions CSC 505 Spring 2005 Week 5 Lectures page 3 The assumption holds if all elements are distinct and all permutations are equally likely or if we use randomized Quicksort in which the pivot is chosen at random instead of being the last element of the subarray The new edition of the book takes a much slicker approach that involves looking at the expected number of comparisons involving a particular element throughout the whole sorting process I is ith smallest n 7 We can assume that T0 T1 0 The recurrence is as follows 1 Tn n71 T0Tn71 1 g Tlt1gtTltn 7 2 1 g Tm 71gt T0 2 n71 n71Tz We can guess that this is Onlgn and prove it by induction similarly we can prove 9n lg n or we can use some algebraic tricks on the recurrence itsel Guess and prove by induction We can show by induction that Tn S anlgn for some constant a gt 0 This is certainly the case for n 0 and n 1 We assume it to be true for all k lt n and show that it holds for n as well with a speci c a to be chosen later Tn n71Ti 2 n71 S n 7 1 7 Zailgi by induction hypothesis n i 1 2a n71 71 7 39l 39 n n 22 g2 2 1 1 S n 7 1 7a lt n2 lgn 7 n2gt by an argument shown below n n71anlgn7in 4 S anlgn as long as a 2 4d The important thing here is that we end up with the same constant a that we started with Consider for example the following awed proof that Tn is CSC 505 Spring 2005 Week 5 Lectures page 4 As before assume that Tk S ak for all k lt n the basis is trivial Tn n71Ti 2 n71 S n 7 1 7 Z ai by induction hypothesis n 1 2a n71 n 71 Z 2 11 1 21 n E n n 2 2 n 71 an 7 a S e an hey its just a constant times n so On right Wrong Bound on Eilgz n71 MQF1 n71 Zilgi Z ilgi Z ilgz39 i1 i1 in21 wt2171 n71 S lgn71 Z ilgn Z i i1 in21 n71 M214 lgnZi7 Z 2 i1 i1 lt nn71lgn7ltg71g 12 1 n2lgn 7 gm 1 Algebraic tricks for history elimination 2 n71 T 71 7 T 39 n n n lt2 n72 2 Tn71 n72 QT2 nTn 7 n 71Tn 71 2Tn 71 1 7 n 71n 7 2 nTn n1Tn712n71 Tn Tn 71 2n 71 n 1 n nn 1 Now let Bn denote 1 Which means that Bn 7 1 is Tn 7 This gives us a much simpler linear recurrence one With no history CSC 505 Spring 2005 Week 5 Lectures page 5 7 2n 7 1 Bn 7 Bn71nn1 Solving this recurrence is straightforward 7 2n 7 1 Bn 7 Bn71nn1 B1 0 7 2239 7 1 Bl iz 1 lt Zn 2 throw awa the 71 7 i2 i71 y n1 1 2 7 S 2lnn 1 7 ln2 i3 2 So Bn E Olg n implies Tn E 0nlg A similar argument can be used to show that Bn E Qlg n and therefore Tn E 9nlg Here s a recap of the solution method 1 Tn n71 E21 needed to get rid of summation 77history so subtracted Tn71 from l Let Bn 1 that gave a recurrence with no history Solved Bn recurrence to get Bn E Olg Substituted back to get Tn Bn n 1 which is in On lg n eww A Completely Different Approach Another way to look at the behavior of Quicksort is to consider cost from the point of view of each possible pair of keys In this approach7 the expected cost is the sum over all pairs 0 probability that there is a comparison involving this pair gtlt cost of 1 comparison What is the probability that a comparison occurs between 11 and zj the ith and jth key in the nal sorted order assume 239 lt j 7 Consider the set of keys 117 n1 l l l 7 M71 1 As soon as any one of these keys is chosen as pivot7 11 and zj will no longer be in the same partition and can no longer be compared The last time all keys of the set occur in the same partition7 there is a probability of 20 7 i 1 that 11 or zj is the pivot and therefore 11 and zj will be compared In all other cases7 they will never be compared So the expected number of comparisons is 20771 7 Z 20771 i1ji1 all pairs 13 n71n7i n71 n letting k j 7239 22mm 1 g 22 2n71Hn e 0nlgn i1k1 i1k 1 Lower Bounds There are several types of lower bounds that are relevant in algorihm analysis All are described in terms of bigomega notationl ll A lower bound on a function 7 for example one described by a recurrence relation such as Tn n 2221 and Tl 0 We can state without knowing anything about where Tn came from that Tn E 9nlg If Tn is an accurate description of the number of basic operations worst or averagecase of some algorithm then the lower bound also applies to the algorithm 2 A lower bound on the worstcase performance of an algorithml For example if we can show that there exist c gt 0 and no such that for all n 2 no there exists at least one input of size n that causes heapsort to perform cnlgn comparisons we can say that the worstcase number of comparisons for heapsort is 9nlgn l Important we must exhibit a method for constructing bad inputs to justify our pessimism 3 A lower bound on all algorithms solving a given probleml In the case of sorting for example what we would have to prove is For any sorting algorithm A there exist c gt 0 an The worstcase example for a given n may differ for different algorithms but every algorithm must have such an example for every no In general it is impossible to prove such a statement We usually need to restrict the class of algorithms we are willing to consider so that we can devise a mathematical model for the behavior of a generic algorithml Comparisonbased algorithms A lower bound that applies to all comparisonbased algorithms is based on the assumption that the only method by which the algorithm accesses a key is to compare two keys with each ot erl Generalpurpose sorting algorithms are required to obey this assumption For example the Unix sort utility in the CC library requires a functionpointer argument for specifying the key comparison methodl Therefore the implementation of the utility cannot access the keys directlyl An adversary argument One model for proving worstcase lower bounds involves an adversary playing against77 an arbitrary algorithm and using a strategy that forces as many comaprisons as possible to take place as pictured belowl kay1ltka algo thm Adversary makes a series forces algorithm of compansons any comparisons as possible yesno For example suppose we are sorting three distinct keys 11 12 and 13 There are 6 possible permutations r1 lt r2 lt r3 r1 lt r3 lt r2 r2 lt r1 lt r3 r2 lt r3 lt r1 r3 lt r1 lt r2 Iglt I2 lt11 The algorithm might begin by asking whether 11 lt 12 doesn t matter 7 all comparisons are equivalent at this point Regardless of what the adversary answers exactly 3 possible permutations are eliminate The adversary s answer to the next comparison however is critical to their strategy One answer might eliminate 2 permuations while the other eliminates only one The adversary must pick the lat ter to force the algorithm to do a third comparison if the algorithm does not do another comparison it cannot decide which permutation is the correct one i The adversary has a simple strategy that will work against any comparisonbased sorting algorithm whenever the algorithm makes a comparison choose the answer that will eliminate the fewest possible permutations If there are n keys instead of 3 there are initially nl possible permutationsi After the algorithm has done k comparisons the adversary can guarantee that lnlZkl permutations will still be possible If the algorithm claims to be done sorting when lnlZkl gt 1 the adversary can always reveal values for the keys that are consistent with all k answers but not with the sorted order produced by the algorithmi So the algorithm is not done until lnlle S 1 This translates to 2k 2 ml or k 2 llgnl li It is not hard to show as you7ve already done in homework that lgnl lgnn 7 ln 7 2 l ELI lgi is 9nlgn n n n n Zlgi 2 lgi 2 5 lg a 2 Z lgn for suf ciently large n i1 Si n Thus any comparisonbased sorting algorithm must do at least llgnll E 9n lg n comparisonsi Decision trees Any comparisonbased algorithm can be represented by a decision tree that shows all possible se quences of comparisons that the algorithm could make Each interior node of a decision tree repre sents a single comparison The two children of a node represent the two outcomes of the comparison yesno truefalse Each leaf represents a possible output In the case of sorting algorithms the outputs are the permutations of the keys again we assume all keys to be distinct For example the decision tree representing insertion sort of 3 keys is shown belowi CSC 505 Spring 2005 Week 2 Lectures page 1 of 8 Objectives 0 learn how recurrence relations are derived from divideand conquer algorithms 0 learn techniques for solving recurrences Divideandconquer recurrences To solve an instance of a problem P IF the instance of P is large enough77 THEN 0 Divide the instance of P into smaller instances of the same problem at a cost of gn o Recurse to solve the smaller instances S aTnb7 if there are a instances of size S nb 0 Combine solutions of the smaller instances to create a solution for the original instance at a cost of hn o Solve the instance of P directly ENDIF ELS So the total cost of the algorithm is governed by the recurrence relation Tn S aTnb gn hn if n gt s and S e0 otherwise We get similar recurrences if we have a lower bound on the number of operations execution time or an exact va uel Simple example Binary search If we count the number of comparisons7 Tn 1 in the worst case if n gt 1 and Tl 1 By brute force7 Tltngt Mgr 1 Mgw l as longasn22i soimk Snlt2k1 then Tm T23k1k1k1 ngnjl Another example Mergesort Recall the algorithm Based on notes by Dr Carla D Savage All rights reserved CSC 505 Spring 2005 Week 2 Lectures page 2 IF the array has more than one element THEN 0 Divide the array in half conceptually o Recurse to sort both the lower half and the upper half 0 Combine the two sorted halves by merging them ELSE 0 Do nothing ENDIF Assume for simplicity that n is a power of two if not the problem size is at most doubled by padding the input to the next power of 2 and the total time will only be affected by a constant factor 7 this works assuming the time is polynomial in Again we count comparisons Tn 2Tn2 n 71 if n gt 1 and Tl 0 Brute force approach Tm mg n 71 2 2TZn271 7171 4mg 2717 3 2iTini2il aslongasn22i Soifn2k thenTn2kTkni2klnlgn7nli The pattern may not be obvious and it s easy to make algebraic mistakes that would put you completely on the wrong track Here s an alternate approach that works much better Recursion tree method Tn Level 0 Tn2 Tn2 Level 1 TMK Level 2 m I Tn2Z Tn2Z Tn2Z Tn2l Level 239 T0 T0 T0 T0 Level k 2kn copies The tree diagrams all the recursive calls that take place What is missing is an account of the operations that take place within each call In this situation level Is is trivial 7 Tl 0 so there are no comparisons at this level For the remaining levels it is helpful to construct a table once you get better at this the table won t be necessary but the tree is still usefu CSC 505 Spring 2005 Week 2 Lectures page 3 Level of instances instance size cost per instance total cost 0 1 n 7 2k n 7 1 n 7 1 1 2 712721 1 n271 n72 2 4 714721 n471 n74 239 2i l n2i 7 2 n2i 71 l n 7 2i k 2k l 71216 1 l 0 l 0 The total cost number of comparisons for the algorithm is the sum over all the levels of the total cost at each leve 1 71 Tn Zni2i0kn72kilnlgninl i0 levelk all but level k A more interesting example Matrix multiplication Strassen7 in 19697 discovered a way to do 2 X 2 matrix multiplication in 7 instead of 8 scalar multiplications1 Not a big deal7 but 1 1 1 His method generalized to the following situation 011 012 A11 A12 B11 B12 021 022 A21 A22 B21 B22 where the Aij Bij and Cij are n2 gtlt n2 matrices instead of scalars1 In other words7 multiplication of two n X n matrices could be expressed in terms of 7 multiplications of two n2 gtlt n2 matrices plus some addition and subtraction of n2 gtlt n2 matrices The recurrence for the number of scalar operations addition and multiplication is Tn 7 Tn2 15n24 when n gt1 and Tl 1 The recursion tree is as follows Tn Level 0 712 Tn2 Tn2 Tn2 Tn2 Tn2 Tn2 Levell T Tn4 Tn4 Leve2 Tn2iTn2i Tn2iTn2igt Leveli T1 T1 T0 T0 Levelk 2k7n copies And the table is CSC 505 Spring 2005 Week 2 Lectures page 4 Level of instances instance size cost per instance total cost 0 1 n 2k 15n24 15n24 1 7 n2 2111 1571244 715n244 2 49 n4 2H 15n24 16 4915712416 239 7i n2i 21H 15n24 22139 7i 15n24 22139 k 7k l 7121c 1 l 1 l 7k The total cost number of scalar operations for the algorithm is the sum over all the levels of the total cost at each level 6 1 7 i I 2 I 2139 k 7 Tn 7 27 15m 4 2 7 10 level k all but level k General divide andconquer recurrences 1n the more general situation the divideand conquer algorithm divides an instance of size n into a instances of size nb welll assume n bk to keep the analysis simple and the total number of operations required for the dividing and the recombining is when n gt 8 So the recurrence is Tn aT when n gt s and Tn e0 otherwise In most of our analyses 8 1 and we assume this in what follows The results are not signi cantly affected if s gt 1 The analysis might put Tn between two constants for n S s but the 9 bound is not affected we can simply use one constant for bigoh the other for bigomega The tree method when carried out for the general situation has ai instances at level i The size of each instance is nbi and the total number of operations at level i is aifnbi1 At level k we have ak instances of size 1 for a total cost of eoaki Let7s make another simplifying assumption 7 suppose that Id for some d gt 0 The total cost of the algorithm 1s 171 I I 1671 I 17 abdk Tltngt soak gembl nd Zwbdr MW i0 i0 with the last equality holding only if a 12d We consider three possibilities k 2 1 lt a Tn eoak elnd bum 7 1 E 9ak C1 is constant and recall that n bk 2 1 a Tn eoak knd 6 nd lg n ak bdk nd here formula for series is invalid 2 1 gt a Tn S eoak elnd 6 nd cl is constant ak lt bdk nd 1n the rst case C1 is simply the denominator of the fraction 1n the third case it comes from the fact that something very close to 1 the numerator is being multiplied by a constant the denominator The analysis of the all these cases obviously holds if E zd CSC 505 Spring 2005 Week 2 Lectures page 5 The analysis for the rst case still holds if E 0zd Then we can say Tn eoak gn where gn Eoltiltk71 aifnbi S C0 C1 Ekoltiltkil ainbdi E 0ak Here C0 is a bound on the cost of all instances whose size is less than the no used to prove E 0zd and C1 is the e of that proof In the third case suppose E 9zd We want to bound gn in terms of because is now the dominant term for the growth rate That gn E is obVious 7 the rst term of gn is To prove that gn E we assume that satis es a technical condition true of Virtually anything you re likely to encounter in algorithm analysis there exists a e lt 1 such that afnb S for all n gt I Then aifnbi S and gn S Eoltiltkileifn S K 20 Ci fn1 C The argument on the third case works even is not a power of b an issue that is revisited later The three cases are the three cases of the Master Theorem Theorem 41 in Section 43 An alternate way to look at the summation 6 1 6 1 Dombi Zaimb d 7 kil Tld ZWl y which is Tld times a constant if a lt 2 1 because of i0 the geometric series with ratio lt l 71 0r ak Zai kbk id since n 12d i0 k ak Zazday which is ak nlogba times a constant if a gt 2 1 j1 71 0r 7Lle ndlogbn ifa 12d i0 When to use the Master Theorem The Master Theorem stated in table form goes as follows lf Tn aTnb for n gt s and co otherwise and H l E Onl gba 5 for some 6 gt 0 Tn E nl gba lt2 1 e ewe M e eltfltngt 1m 3 E 9n103b 5 for some 6 gt 0 Tn E The regularity condition for case 3 is There exist e lt l and no gt 0 such that a S e Examples when a b 2 so the recurrence is Tn 2Tn2 where is one of the following CSC 505 Spring 2005 Week 2 Lectures page 6 f case Tn comments 5 l n e 05 works lgn l n any 6 lt 05 works nlgn2 none limnnoonlgn2n1 5 limnn00 nelg n 00 n 2 n lg n nlgn none limnn00 n lg nn16 limnn00 lg nne 0 n lgny 3 n lg n2 any 6 lt 05 works n 3 e 05 works What to do when it doesn t apply Consider the case Tn 2Tn nlgn as in the table above let 8 l and Tl Co The recursion tree for all examples in the above table is the same 7 number of instances doubles at each level while the problem size is cut in half A table analysis of the cost gives Level of instances instance size cost per instance total cost 0 l n 2k nlgn nk nk l 2 n2 2116 1 lgn2 n2k 7 l nk 7 l 2 4 n4 2k 2 lgn4 n4k 7 2 nk 7 2 i l 2139 n2i 217i n2i1gn2i TL260 7239 nk7 2 k 2k n2k l e0 e0 n The solution is 71 k k k l Tn e0 n Zn c 7 n Co n co E nlgn2 i0 j1 Another situation from earlier where the Master Theorem does not apply is Tn 2Tn2 n lg n Level of instances instance size cost instance total cost 7 CSC 505 Spring 2005 Week 2 Lectures page 7 The solution is 71 k 1 00 1 Tn0039nZnkii2n 00Zj72 Sn 60Zj72 69n i0 j1 j1 00 because 21 converges to a xed value 7 the ratio test applies llmjaoo j2j D2 0 lt 1 j1 Recurrences that don t t the usual pattern The recursiontree method applies even to situations that don7t look anything like that of the Master theoreml For example7 suppose we want a bound on Tn 2Tn 7 3 W when n gt 2 and T0 Tl T2 e0 Tn Level 0 Tn 7 3 Tn 7 3 Level 1 Tn 7 6 Tn 7 6 Tn 7 6 Tn 7 6 Level 2 H Tn73i Tn73i Tn73i Tn73i Levelz39 Tc Tc M M Level 16 2k copies where e52 and k to be determined Here k is the smallest value ofi for which n 7 3239 S 27 namely 7 and Te 5 This gives us the following table analysis Level of instances instance size cost per instance total cost 0 1 n 2k J5 1 2 n 7 3 m 2H 2 4 n 7 6 m 4H il 2139 l n73i l m pigm kl 2k l elt2 l 5 l 5216 71 Tm c0 216 22271 7 32 g 2 w e OwlWE 10 A bigomega bound can be derived similarlyl When n is not a power of b When n is not a power of 127 we need to go back to the fact that the original situation in which the recurrence arose is really best described by CSC 505 Spring 2005 Week 2 Lectures page 8 Tn S aTUnbl eUfn and Tn 2 aTQnbj eLfn when n gt 8 What follows is the bigoh proof for Tn under the Master theorem 7 the bigomega proof is almost identical 7 n if j 0 V j De ne nj 7 milb if gt 0 It 1s easy to show page 83 that n S nb bb 71 Let k Llogb Then nk is constant and so is Tnk eg to give it a name Based on recursion tree analysis we conclude that 71 Tn S eBnlogba CU Zaj nj j0 Letls look at case 17 where E 0nd where d logb a 7 6 case 2 is very similar and given on pages 8384 case 3 is a lot easier First we put a bound on in terms of nd 7 711 S TlV bb1 4011700 MWb 1d CndVd1 MWb 1d CndVd1 bb 1 endbjd l The summation can then be bounded as follows 7 71 71 aj 39 d th nj S 6 2 J l x 3 l m g 3 and case 1 is Onl gba as desired CSC 505 Spring 2005 Week 1 Lectures page 1 of8 Objectives overview of policies procedures and course material deal with simple examples of algorithm analysis learn notation for growth of functions big oh big omega etcl look at a simple example of divide and conquer our first algorithm design technique CSC 505 focus is on solving problems ef ciently on a computer resources are time and space D Algorithm design techniques D Algorithm analysis techniques D Data structures D Problem complexity inherent dif culty Some useful formulae You should be familiar with these already Please review them and be sure you understand how each can be prove 7 log n 1 loga n 7 log a 2 zloga y yloga as n nn l 3 Z 7 2 H nn l2n 1 6 M3 N m 4 H 17 21 5 1 1mm is H H o t otherwise al 7 ak 7 kak1 l 7 a2 l 7 a 6 Mr N ms H o 7 Mg 3 H o 1 7 a2 Analysis As an indicator of execution time determine the number of basic operations as a function of problem size Based on notes by Dr Carla D Savage All rights reserved CSC 505 Spring 2005 Week 1 Lectures page 2 Example 1 Square Matrix Multiplication cm cm Cnn am am am bnl bn2 bnn Where n Cij E aikbkj k1 Problem size is n 7 by convention You could argue for 2n2 since there are 2n2 distinct scalar inputs7 but that makes the algebra complicated Basic operations are scalar multiplication and addition An algorithm for matrix multiplication for 239 lt7 l to n do forj lt7 l to n do eij lt7 0 for k lt7 l to n do elm H CW all kl Wm Number of scalar multiplications is 7 Number of scalar additions is 7 Example 2 Linear Search Determine Whether I is one of AH AB 7 AM and retrieve other information about Problem size is n Basic operation compare 1 With an element of array A Algorithm 239 lt7 1 While g n and y I do i lt7 il if i gt n then i lt7 0 D return a 0 if z is not found Number of comparisons is 7 Worst case 7 Best case 7 Average case 7 Example 3 Insertion Sort Arrange AH 7 AM in ascending order numerically or lexicographically Problem size is n Basic operation compare two elements of A CSC 505 Spring 2005 Week 1 Lectures page 3 Algorithm Insertion Sort 1 J 7 2 D lNVARlANT AH AU 7 l are in ascending order 2 while j S n do D Insert AU into its proper position among AH AU 71 3 I H Aljl 7171 D lNVARlANT AU lt AM for all k satisfying 239 l S k S j 7 l 4 while gt 0 and gt I do 5 Ai1 A Aii A 2 71 6 Ai1 lt7 z 7 lt7 jl Aside about loop invariants A loop invariant is a logical assertion that is true immediately before the loops condition is tested no matter how many iteraions of the loop are performed It can be written as a comment before the While statement To be a valid invariant the assertion must satisfy two conditions 1 It must be true right before the rst iteration of the loop usually in a trivial way For example because j 2 after line 1 the outer loop invariant says that AD is in ascending order 2 Truth of the assertion at the beginning of a loop iteration must imply truth at the end For example when AD is inserted into the proper place among Al Aj7l then Al Aj will be in ascending order After line 7 it will still be the case that Al AU 7 l are in ascending order To be useful the assertion must satisfy a third condition 3 The invariant along with the negation of the loop condition should imply the correctness of the algorithm or some other useful property of the algorithm For example the loop condition for the outer loop is j S n lts negation is j gt n j gt n and Al AU 7 l are in ascending order then the array is in sorted order To establish complete correctness of the algorithm we also have to prove that AH AM at the end of the algorithm are the same set as at the beginning Number of element comparisons Worst case Best case 7 Average case 7 Approach A Use summation to account for number of basic operations in each loop In the worst case the inner loop lines 45 requires j 7 l comparisons that is what happens ifi reaches 0 or 1 before we exit the loop The outer loop is executed for values ofj ranging from 2 to n so the total is n n71 nn 71 20 71 Z 2 12 11 Approach B The number of comparisons in each inner loop is the number of shifts times when I lt and moves one position to the right If we exit the loop before 239 0 there is an extra comparison CSC 505 Spring 2005 Week 1 Lectures page 4 with no corresponding shift but this does not affect the worstcase analysis Each shift occurs because of an inversion a pair of elements that were in the wrong order initially ie a pair ij with 1 S i lt j S n for which gt AD in the original input array This means that the number of comparisons in insertion sort is the number of inversionsl 1n the worst case every pa1r 1s an 1nversion and the number of inverslons 1s the number of pa1rs 2 nn 7 12l Asymptotic growth rate analysis A further abstraction that we use in algorithm analysis is to characterize functions recall that number of basic operations a measure of time is expressed as a function of input size in terms of growth classes Matrix multiplication time grows as n3 Linear search time grows as n lnsertion sort time grows as n2 or k where h number of inversions Why is growth rate important Actual execution time assuming 1000000 basic operations per second Execution time where n input size input size 300 n 46 nlgn 65 n2 017 n3 00001 2 10 003 sec 10015 sec 100065 sec 100017 sec lt 1000001 sec 100 103 sec 103 sec 065 sec 117 sec 4 X 108 centuries 1000 3 sec 145 sec 65 sec N 3 min N 00 104 3 sec 61 sec N 11 min N 2 days N 00 105 30 sec 13 min N 18 hours N 65 years N 00 and now problem size as a function of available time 1 sec 3333 2000 392 180 39 1 sec 10X7 33333 16000 1240 388 43 1 min 200000 82000 3038 706 45 1 min 10X 2000000 700000 9607 1521 49 from Jon Bentley Programming Pearls Via Sara Baase Computer Algorithms adapted brunning on a 10 times faster machine Growth classes of functions Ogn big oh upper bound on the growth rate of a function that is a function belongs to class Ogn if gn is an upper bound on its growth rate big omega lower bound on the growth rate of a function gn big theta exact bound on the growth rate of a function ogn little oh used to denote functions that grow more slowly than gn for example sometimes it s useful to characterize the number of basic operations as something like 3n 0n to indicate that it s On with a small leading constant wgn little omega denotes functions that grow faster than gn rarely used but included for completeness For example a function describing the worst case number of basic operations of an algorithm might be On2 and 9nlgn since its difficult to pin down exactlyl CSC 505 Spring 2005 Week 1 Lectures page 5 If we nd that there s a set of example inputs for which the growth rate in number of basic operations is n2 then we can also say it s 9n2 the fact that its 9nlg n is still true and conclude that its nQ If on the other hand we7re able to prove that it never grows faster than nlg n we can say that its On lg n the fact that its On2 is still true and conclude that its nlg Precise de nitions of big oh and big omega E Ogn iff there exist e gt 0 and no gt 0 such that S egn for all n 2 not E iff there exist e gt 0 and no gt 0 such that 2 egn for all n 2 not 99 O9 0 99 Many authors abuse notation and say Ogn when they mean E Ogn same with and This is not a problemi However many technical papers will incorrectly use Ogn when they mean or For example matrix multiplication requires at least On2 operations possibly as many as On 77 Examples illustrating big oh and big omega n22nlgn E 0n3 Proof n22nlgn S n22nn as longaanl n2 3n S n33n3 ifn 21 4n3 This satis es the de nition of On3 with e 4 and no l n3 7 10n2 g 0n2 Proof Otherwise there must exist e gt 0 and no gt 0 with n3 7 10n2 S en2 for all n 2 not But then n3 S e lOn2 for all n 2 no and n S 0 10 The latter is impossible for a given e and all n 2 not 5n3 7 3n2 2n 7 6 6 ng Proof First show that its in On3 5n373n22n76 S 5n32n S 7n3 when n 2 1 so it s On3 with e 7 and no 1 Then that it s in 9n3 5n373n22n76 2 5n373n276 2 gng when gng 2 3n2 6 or n 2 2 good enough Of course the above examples are only meant to emphasize the de nition and illustrate what must be proved in order to claim time bounds in particular growth class The examples seem to suggest that we gure out the exact number of basic operations as a function of n the input size and then ii prove that what we gured out belongs to a particular growth classi CSC 505 Spring 2005 Week 1 Lectures page 6 In fact we can simplify analysis by skipping step Recall insertion sorti We know the number of comparisons is On2 7 there are at most n iterations of the outer loop and at most n of the inner oop We can also argue 9n2 7 for the last iterations of the outer loop j is at least n2l In the worst case when AD is less than all of All i AU 7 1 there are j 7 l iterations of the inner loop and the worst case happens every time when the array is in reverse order So the number of comparisons is at least n2n2 71 n24 7 n2 which is 2 n28 when n 2 4 do the math Examples involving logarithms and exponents ln n 6 lg n Proof Recall that lnn loge n and lgn log2 n Using one of the mathematical identities on the rst page we have So elgn S lnn S elgn where e for all n 2 l which proves both Olg n and Qlg lgei e g On for any xed ti Proof Otherwise there exist e gt 0 and no gt 0 with e S en for all n 2 not But then taking natural logs of both sides n S lne tln n This translates into divide each side by ln n l i S tS lnet whenn 2 e a constant lnn lnn On the other hand 1 7 lim 7 00 what rule did we use n7gtoo Inn n7gtoltgt l n Little oh and little omega E 0gn iff for all e gt 0 there exists no gt 0 such that 0 S lt egn for all n 2 not E wgn iff for all e gt 0 there exists no gt 0 such that 0 S egn lt for all n 2 not Observations 6 M901 15901 E 0f o E 0gn implies g o E wgn implies g Ogn For example Proof limnanS 0 and by de nition of limit for any e gt 0 there is an no gt 0 with 23 lt e for all n 2 not This means that 2 lt 03 for all n 2 no as desired Limits and asymptotic notation l39m M 0 implies E 0gn that is g an gm CSC 505 Spring 2005 Week 1 Lectures page 7 in 00 implies E wgn7 that is7 g Ogn whine d gt 0 implies E gn So limits can be helpful in determining the growth rate of functions Warning The converses of the above are not necessniily true Limits may not exist in some cases where growth classes are wellde ned You might be tempted to conjecture that 0gn Ogn 7 Not so Consider the following functions as suggested by the drawing Here assuming constants have been appropriately scaled7 E Ogn but g it keeps dipping down77 to 07 so E Ogn 7 But g 0gn it keeps rising back up77 to the value of DIVIDE AND CONQUER To solve an instance of a problem P IF the instance of P is large enough77 THEN 0 Divide the instance of P into smaller instances of the same problem 0 Recurse to solve the smaller instances 0 Combine solutions of the smaller instances to create a solution for the original instance ELSE o Solve the instance of P directly ENDlF CSC 505 Spring 2005 Week 1 Lectures page 8 Example Binary search Search for key I in a sorted array AH i i i Ani IF the array has more than one element THEN 0 Divide the array in half conceptually Compare 1 with the last element of the lower half 0 if z is larger7 then reourse to search for z in the upper half else recurse to search for z in the lower half 0 return the result of the recursive search there is no real combine step 7 this is toil recursion and can easily be implemented as a oop ELSE 0 Compare the single element to z and return index if theylre equal ENDlF Details function BINARYSEARCHA7 I lower7 upper is D returns index of I if z is one of Alower7 i i i Aupper D or 0 if it isnlti D lnitially called with lower l and upper n if lower lt upper then mid lt7 Llower upper2j if I g Amid then return BINARYSEARCHA as lower mid else return BINARYSEARCHA 1 mid 1 upper else D lower upper if z Alower then return lower else return 0 D Not found end BINARYSEARCH Recursive insertion sort as a way of introducing mergesort IF the array has more than one element THEN 0 Divide the array into two parts7 one that includes only the last element7 the other the remaining elements 0 Recurse to sort all but the last element 0 Combine by inserting the last element into the recursively sorted arrayi ELSE 0 Do nothing a oneelement array is already sorted ENDlF Mergesort IF the array has more than one element THEN 0 Divide the array in half conceptually o Recurse to sort both the lower half and the upper half 0 Combine the two sorted halves by merging themi ELSE 0 Do nothing ENDlF
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'