example we would like to prove that function fact does indeed compute the factorial function there are two distinct steps to such proof the first is to prove that the function always terminates the second is to prove that the function returns the correct value theorem function fact will terminate for any value of prooffor the base casewe observe that fact will terminate directly whenever < the induction hypothesis is that fact will terminate for for nwe have two possibilities one possibility is that > in that casefact will terminate directly because it will fail its assertion test otherwisefact will make recursive call to fact( - by the induction hypothesisfact( - must terminate theorem function fact does compute the factorial function for any value in the range to proofto prove the base caseobserve that when or fact(nreturns the correct value of the induction hypothesis is that fact( - returns the correct value of ( )for any value within the legal rangefact(nreturns fact( - by the induction hypothesisfact( - ( )!and because ( ) !we have proved that fact(nproduces the correct result we can use similar process to prove many recursive programs correct the general form is to show that the base cases perform correctlyand then to use the induction hypothesis to show that the recursive step also produces the correct result prior to thiswe must prove that the function always terminateswhich might also be done using an induction proof estimating one of the most useful life skills that you can gain from your computer science training is knowing how to perform quick estimates this is sometimes known as "back of the napkinor "back of the envelopecalculation both nicknames suggest that only rough estimate is produced estimation techniques are standard part of engineering curricula but are often neglected in computer science estimation is no substitute for rigorousdetailed analysis of problembut it can serve to indicate when rigorous analysis is warrantedif the initial estimate indicates that the solution is unworkablethen further analysis is probably unnecessary estimating can be formalized by the following three-step process determine the major parameters that affect the problem