1 Exercises and Solutions - Auckland

1 1 Exercises and SolutionsMost of the Exercises below have Solutions but you should try first to solvethem. Each subsection with Solutions is after the corresponding subsectionwith Exercises . Time complexity and Big-Oh notation: exercises1. A sorting method with Big-Oh complexityO(nlogn) spends exactly 1millisecond to sort 1,000 data items. Assuming that timeT(n) of sortingnitems is directly proportional tonlogn, that is,T(n) =cnlogn, derivea formula forT(n), given the timeT(N) for sortingNitems, and estimatehow long this method will sort 1,000,000 A quadratic algorithm with processing timeT(n) =cn2spendsT(N)seconds for processingNdata items. How much time will be spent forprocessingn= 5000 data items, assuming thatN= 100 andT(N) = 1ms?

2 3. An algorithm with time complexityO(f(n)) and processing timeT(n) =cf(n), wheref(n) is a known function ofn, spends 10 seconds to process1000 data items. How much time will be spent to process 100,000 dataitems iff(n) =nandf(n) =n3?4. Assume that each of the expressions below gives the processing timeT(n)spent by an algorithm for solving a problem of sizen. Select the dominantterm(s) having the steepest increase innand specify the lowest Big-Ohcomplexity of each term(s)O(..)5 + + + + + + +n(log2n)2nlog3n+nlog2n3 log8n+ log2log2log2n100n+ + 100n22n+ + +n(log2n)2100nlog3n+n3+ log4n+ log2log2n15. The statements below show some features of Big-Oh notation for thefunctionsf f(n) andg g(n). Determine whether each statement isTRUE or FALSE and correct the formula in the latter it TRUEor FALSE?

3 If it is FALSE then writethe correct formulaRule of sums:O(f+g) =O(f) +O(g)Rule of products:O(f g) =O(f) O(g)Transitivity:ifg=O(f) andh=O(f)theng=O(h)5n+ 8n2+ 100n3=O(n4)5n+8n2+100n3=O(n2logn)6. Prove thatT(n) =a0+a1n+a2n2+a3n3isO(n3) using the formaldefinition of the Big-Oh :Find a constantcand thresholdn0such thatcn3 T(n) forn AlgorithmsAandBspend exactlyTA(n) = (n) = , respectively, for a problem of sizen. Choose the al-gorithm, which is better in the Big-Oh sense, and find out a problem sizen0such that for any larger sizen > n0the chosen algorithm outperformsthe other. If your problems are of the sizen 109, which algorithm willyou recommend to use?8. AlgorithmsAandBspend exactlyTA(n) =cAnlog2nandTB(n) =cBn2microseconds, respectively, for a problem of sizen.

4 Find the best algorithmfor processingn= 220data items if the algoritmAspends 10 microsecondsto process 1024 items and the algorithmBspends only 1 microsecond toprocess 1024 AlgorithmsAandBspend exactlyTA(n) = 5 n log10nandTB(n) = 25 nmicroseconds, respectively, for a problem of sizen. Which algorithm isbetter in the Big-Oh sense? For which problem sizes does it outperformthe other?10. One of the two software packages,AorB, should be chosen to processvery big databases, containing each up to 1012records. Average process-ing time of the packageAisTA(n) = n log2nmicroseconds, and theaverage processing time of the packageBisTB(n) = 5 algorithm has better performance in a Big-Oh sense? Work outexact conditions when these packages outperform each One of the two software packages,AorB, should be chosen to processdata collections, containing each up to 109records.

5 Average processingtime of the packageAisTA(n) = and the averageprocessing time of the packageBisTB(n) = 500 nmilliseconds. Whichalgorithm has better performance in a Big-Oh sense? Work out exactconditions when these packages outperform each Software packagesAandBof complexityO(nlogn) andO(n), respec-tively, spend exactlyTA(n) =cAnlog10nandTB(n) =cBnmillisecondsto processndata items. During a test, the average time of processingn= 104data items with the packageAandBis 100 milliseconds and 500milliseconds, respectively. Work out exact conditions when one packageactually outperforms the other and recommend the best choice if up ton= 109items should be Let processing time of an algorithm of Big-Oh complexityO(f(n)) bedirectly proportional tof(n).

6 Let three such algorithmsA,B, andChave time complexityO(n2),O( ), andO(nlogn), respectively. Duringa test, each algorithm spends 10 seconds to process 100 data items. Derivethe time each algorithm should spend to process 10,000 Software packagesAandBhave processing time exactlyTEP= , respectively. If you are interested in faster processing ofup ton= 108data items, then which package should be choose? Time complexity and Big-Oh notation: solutions1. Because processing time isT(n) =cnlogn, the constant factorc=T(N)NlogN,andT(n) =T(N)nlognNlogN. Ratio of logarithms of the same base is indepen-dent of the base (see Appendix in the textbook), hence, any appropriatebase can be used in the above formula (say, base of 10). Therefore, forn= 1000000 the time isT(1,000,000) =T(1,000) 1000000 log1010000001000 log101000=1 1000000 61000 3= 2,000 ms2.

7 The constant factorc=T(N)N2, thereforeT(n) =T(N)n2N2=n210000ms andT(5000) = 2,500 The constant factorc=T(1000)f(1000)=10f(1000)millisec onds per item. There-fore,T(n) = 10f(n)f(1000)ms andT(100,000) = 10f(100,000)f(1000)ms. Iff(n) =nthenT(100,000) = 1000 ms. Iff(n) =n3, thenT(100,000) = term(s)O(..)5 + + (n3)500n+ + ( ) + + ( )n2log2n+n(log2n)2n2log2nO(n2logn)nlog3n +nlog2nnlog3n,nlog2nO(nlogn)3 log8n+ log2log2log2n3 log8nO(logn)100n+ (n2) + 100n2100n2O(n2)2n+ + ( ) +n(log2n)2n(log2n)2O(n(logn)2)100nlog3n+ n3+ 100nn3O(n3) log4n+ log4nO(logn) it TRUEor FALSE?If it is FALSE thenwritethe correct formulaRule of sums:O(f+g) =O(f) +O(g)FALSEO(f+g) =max{O(f), O(g)}Rule of products:O(f g) =O(f) O(g)TRUET ransitivity:ifg=O(f) andh=O(f)theng=O(h)FALSEifg=O(f) andf=O(h) theng=O(h)5n+ 8n2+ 100n3=O(n4)TRUE5n+ 8n2+ 100n3=O(n2logn)FALSE5n+ 8n2+ 100n3=O(n3)6.

8 It is obvious thatT(n) |a0|+|a1|n+|a2|n2+|a3|n3. Thus ifn 1,thenT(n) cn3wherec=|a0|+|a1|+|a2|+|a3|so thatT(n) isO(n3).7. In the Big-Oh sense, the algorithmBis better. It outperforms the algo-4rithmAwhenTB(n) TA(n), that is, when Thisinequality reduces to log10n 25, orn n0= 1025. Ifn 109, thealgorithm of choice The constant factors forAandBare:cA=101024 log21024=11024;cB=110242 Thus, to process 220= 10242items the algorithmsAandBwill spendTA(220) =11024220log2(220) = 20280 s andTB(220) =110242240= 220 s,respectively. BecauseTB(220) TA(220), the method of choice In the Big-Oh sense, the algorithmBis better. It outperforms the algo-rithmAifTB(n) TA(n), that is, if 25n 5nlog10n, or log10n 5, orn 100, In the Big-Oh sense, the algorithmBof complexityO(n) is better thanAof complexityO(nlogn).

9 He packageBhas better performance in aThe packageBbegins to outperformAwhen (TA(n) TB(n), that is,when 5 n. This inequality reduces to log2n 5, orn 250 1015. Thus for processing up to 1012data items, the packageof choice In the Big-Oh sense, the packageBof complexityO( ) is betterthanAof complexityO(n). The packageBbegins to outperformAwhen(TA(n) TB(n), that is, when 500 n. This inequality reducesto n 5 105, orn 25 1010. Thus for processing up to 109data items,the package of choice In the Big-Oh sense, the packageBof linear complexityO(n) is betterthan the packageAofO(nlogn) complexity. The processing times of thepackages areTA(n) =cAnlog10nandTB(n) =cBn, respectively. Thetests allows us to derive the constant factors:cA=100104log10104=1400cB=500104= 120 The packageBbegins to outperformAwhen we must estimate the datasizen0that ensuresTA(n) TB(n), that is, whennlog10n400 n20.))

10 Thisinequality reduces to log10n 40020, orn 1020. Thus for processing upto 109data items, the package of choice to process 10,000 itemsA1O(n2)T(10,000) =T(100) 1000021002= 10 10000 = 100,000 ( )T(10,000) =T(100) 10 1000 = 10,000 (nlogn)T(10,000) =T(100) 10000 log 10000100 log 100= 10 200 = 2,000 In the Big-Oh sense, the packageAis better. But it outperforms thepackageBwhenTA(n) TB(n), that is, when This in-equality reduces 3 (= 100), orn 108. Thus for processingup to 108data items, the package of choice Recurrences and divide-and-conquer paradigm: exer-cises1. Running timeT(n) of processingndata items with a given algorithm isdescribed by the recurrence:T(n) =k T(nk)+c n;T(1) = a closed form formula forT(n) in terms ofc,n, andk.