chap algorithm analysis sum for ( = <=nk*= for ( = <=nj++sum ++/do log times /do times sum for ( = <=nk*= for ( = <=kj++sum ++/do log times /do times when analyzing these two code fragmentswe will assume that is power of two the first code fragment has its outer for loop executed log times because on each iteration is multiplied by two until it reaches because the inner loop always executes plog nn timesthe total cost for the first code fragment can be expressed as = note that variable substitution takes place here to create the summationwith from equation the solution for this summation is th( log nin the second code fragmentthe outer loop is also executed log times the inner loop cost kwhich doubles each time the summation can be expressed phas log as = where is assumed to be power of two and again from equation we know that this summation is simply th(nwhat about other control statementswhile loops are analyzed in manner similar to for loops the cost of an if statement in the worst case is the greater of the costs for the then and else clauses this is also true for the average caseassuming that the size of does not affect the probability of executing one of the clauses (which is usuallybut not necessarilytruefor switch statementsthe worst-case cost is that of the most expensive branch for subroutine callssimply add the cost of executing the subroutine there are rare situations in which the probability for executing the various branches of an if or switch statement are functions of the input size for examplefor input of size nthe then clause of an if statement might be executed with probability / an example would be an if statement that executes the then clause only for the smallest of values to perform an average-case analysis for such programswe cannot simply count the cost of the if statement as being the cost of the more expensive branch in such situationsthe technique of amortized analysis (see section can come to the rescue determining the execution time of recursive subroutine can be difficult the running time for recursive subroutine is typically best expressed by recurrence relation for examplethe recursive factorial function fact of section calls itself with value one less than its input value the result of this recursive call is