algorithm analysis is terribly inefficient the analysis is fairly simple let (nbe the running time for the function call fib(nif or then the running time is some constant valuewhich is the time to do the test at line and return we can say that ( ( because constants do not matter the running time for other values of is then measured relative to the running time of the base case for the time to execute the function is the constant work at line plus the work at line line consists of an addition and two function calls since the function calls are not simple operationsthey must be analyzed by themselves the first function call is fib( - and henceby the definition of trequires ( units of time similar argument shows that the second function call requires ( units of time the total time required is then ( ( where the accounts for the work at line plus the addition at line thusfor > we have the following formula for the running time of fib( ) (nt( ( since fib(nfib( - fib( - )it is easy to show by induction that ( >fib(nin section we showed that fib( ( / ) similar calculation shows that (for fib( >( / ) and so the running time of this program grows exponentially this is about as bad as possible by keeping simple array and using for loopthe running time can be reduced substantially this program is slow because there is huge amount of redundant work being performedviolating the fourth major rule of recursion (the compound interest rule)which was presented in section notice that the first call on line fib( - )actually computes fib( - at some point this information is thrown away and recomputed by the second call on line the amount of information thrown away compounds recursively and results in the huge running time this is perhaps the finest example of the maxim "don' compute anything more than onceand should not scare you away from using recursion throughout this bookwe shall see outstanding uses of recursion solutions for the maximum subsequence sum problem we will now present four algorithms to solve the maximum subsequence sum problem posed earlier the first algorithmwhich merely exhaustively tries all possibilitiesis depicted in figure the indices in the for loop reflect the fact that in ++arrays begin at instead of alsothe algorithm does not compute the actual subsequencesadditional code is required to do this convince yourself that this algorithm works (this should not take much convincingthe running time is ( and is entirely due to lines and which consist of an ( statement buried inside three nested for loops the loop at line is of size the second loop has size iwhich could be small but could also be of size we must assume the worstwith the knowledge that this could make the final bound bit high the third loop has size which again we must assume is of size the total is ( no( line takes only ( totaland lines and take only ( totalsince they are easy expressions inside only two loops