algorithm analysis long long powlong-long xint ifn = return ifn = return xifisevenn return powx xn )else return powx xn xfigure efficient exponentiation without affecting the correctness of the program indeedthe program will still run in (log )because the sequence of multiplications is the same as before howeverall of the following alternatives for line are badeven though they look correct return powpowx ) )return powpowxn ) )return powxn powxn )both lines and are incorrect because when is one of the recursive calls to pow has as the second argument thus no progress is madeand an infinite loop results (in an eventual crashusing line affects the efficiencybecause there are now two recursive calls of size / instead of only one an analysis will show that the running time is no longer (log nwe leave it as an exercise to the reader to determine the new running time limitations of worst-case analysis sometimes the analysis is shown empirically to be an overestimate if this is the casethen either the analysis needs to be tightened (usually by clever observation)or it may be that the average running time is significantly less than the worst-case running time and no improvement in the bound is possible for many complicated algorithms the worstcase bound is achievable by some bad input but is usually an overestimate in practice unfortunatelyfor most of these problemsan average-case analysis is extremely complex (in many cases still unsolved)and worst-case boundeven though overly pessimisticis the best analytical result known summary this gives some hints on how to analyze the complexity of programs unfortunatelyit is not complete guide simple programs usually have simple analysesbut this is not always the case as an examplelater in the text we shall see sorting algorithm (shellsortand an algorithm for maintaining disjoint sets ()each of