from (nto (logn)which is big improvement simple justification techniques sometimeswe will want to make claims about an algorithmsuch as showing that it is correct or that it runs fast in order to rigorously make such claimswe must use mathematical languageand in order to back up such claimswe must justify or prove our statements fortunatelythere are several simple ways to do this by example some claims are of the generic form"there is an element in set that has property to justify such claimwe only need to produce particular in that has property likewisesome hard-to-believe claims are of the generic form"every element in set has property to justify that such claim is falsewe need to only produce particular from that does not have property such an instance is called counterexample example professor amongus claims that every number of the form is primewhen is an integer greater than professor amongus is wrong justificationto prove professor amongus is wrongwe find counterexample fortunatelywe need not look too farfor the "contraattack another set of justification techniques involves the use of the negative the two primary such methods are the use of the contrapositive and the contradiction the use of the contrapositive method is like looking through negative mirror to justify the statement "if is truethen is truewe establish that "if is not truethen is not trueinstead logicallythese two statements are the samebut the latterwhich is called the contrapositive of the firstmay be easier to think about example let and be integers if ab is eventhen is even or is even justificationto justify this cxlaimconsider the contrapositive"if is odd and is oddthen ab is odd sosuppose and + for some integers and then ab ij ( ij plusi henceab is odd