which requires about lines of code the analysis of shellsort is still not completeand the disjoint set algorithm has an analysis that until recently was extremely difficult and require pages and pages of intricate calculations most of the analyses that we will encounter here will be simple and involve counting through loops an interesting kind of analysiswhich we have not touched uponis lower-bound analysis we will see an example of this in where it is proved that any algorithm that sorts by using only comparisons requires ( log ncomparisons in the worst case lower-bound proofs are generally the most difficultbecause they apply not to an algorithm but to class of algorithms that solve problem we close by mentioning that some of the algorithms described here have real-life application the gcd algorithm and the exponentiation algorithm are both used in cryptography specificallya -digit number is raised to large power (usually another -digit number)with only the low or so digits retained after each multiplication since the calculations require dealing with -digit numbersefficiency is obviously important the straightforward algorithm for exponentiation would require about multiplicationswhereas the algorithm presented requires only about , in the worst case exercises order the following functions by growth ratennn log nn log log nn log nn log( ) / / log nn indicate which functions grow at the same rate suppose (no( ( )and (no( ( )which of the following are truea (nt (no( ( ) (nt (no( ( ) (no( (nd (no( ( )which function grows fastern log or log prove that for any constant klogk (nfind two functions (nand (nsuch that neither (no( ( )nor (no( ( )in recent court casea judge cited city for contempt and ordered fine of $ for the first day each subsequent dayuntil the city followed the judge' orderthe fine was squared ( the fine progressed as follows$ $ $ $ $ , what would be the fine on day nb how many days would it take for the fine to reach dollars ( big-oh answer will do)for each of the following six program fragmentsa give an analysis of the running time (big-oh will dob implement the code in the language of your choiceand give the running time for several values of compare your analysis with the actual running times