[PDF] 1.1 Time complexity and Big-Oh notation: exercises

View - Download 1.1 Time complexity and Big-Oh notation: exercises

Previous PDF

Next PDF

1 Exercises and Solutions

Most of the exercises below have solutions but you should try first to solve them. Each subsection with solutions is after the corresponding subsection with exercises. T

1.1 Time complexity and Big-Oh notation: exercises

1. A sorting method with "Big-Oh" complexityO(nlogn) spends exactly 1

millisecond to sort 1,000 data items. Assuming that timeT(n) of sorting nitems is directly proportional tonlogn, that is,T(n) =cnlogn, derive a formula forT(n), given the timeT(N) for sortingNitems, and estimate how long this method will sort 1,000,000 items.

2. A quadratic algorithm with processing timeT(n) =cn2spendsT(N)

seconds for processingNdata items. How much time will be spent for processingn= 5000 data items, assuming thatN= 100 andT(N) = 1ms?

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 process

1000 data items. How much time will be spent to process 100,000 data

items 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 dominant term(s) having the steepest increase innand specify the lowest Big-Oh

complexity of each algorithm.ExpressionDominant term(s)O(...)5 + 0.001n3+ 0.025n500n+ 100n1.5+ 50nlog10n0.3n+ 5n1.5+ 2.5·n1.75n

2log2n+n(log2n)2nlog3n+nlog2n3log

8n+ log2log2log2n100n+ 0.01n20.01n+ 100n22n+n0.5+ 0.5n1.250.01nlog2n+n(log2n)2100nlog3n+n3+ 100n0.003log4n+ log2log2n1

5. The statements below show some features of "Big-Oh" notation for the

functionsf≡f(n) andg≡g(n). Determine whether each statement is TRUE or FALSE and correct the formula in the latter case.StatementIs it TRUE or FALSE?If it is FALSE then write the 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 formal

definition of the Big-Oh notation.Hint:Find a constantcand threshold n

0such thatcn3≥T(n) forn≥n0.

7. AlgorithmsAandBspend exactlyTA(n) = 0.1n2log10nandTB(n) =

2.5n2microseconds, respectively, for a problem of sizen. Choose the al-

gorithm, which is better in the Big-Oh sense, and find out a problem size n

0such that for any larger sizen > n0the chosen algorithm outperforms

you recommend to use?

8. AlgorithmsAandBspend exactlyTA(n) =cAnlog2nandTB(n) =cBn2

microseconds, respectively, for a problem of sizen. Find the best algorithm for processingn= 220data items if the algoritmAspends 10 microseconds to process 1024 items and the algorithmBspends only 1 microsecond to process 1024 items.

9. AlgorithmsAandBspend exactlyTA(n) = 5·n·log10nandTB(n) = 25·n

microseconds, respectively, for a problem of sizen. Which algorithm is better in the Big-Oh sense? For which problem sizes does it outperform the other?

10. One of the two software packages,AorB, should be chosen to process

very big databases, containing each up to 10

12records. Average process-

ing time of the packageAisTA(n) = 0.1·n·log2nmicroseconds, and the average processing time of the packageBisTB(n) = 5·nmicroseconds. 2 Which algorithm has better performance in a "Big-Oh" sense? Work out exact conditions when these packages outperform each other.

11. One of the two software packages,AorB, should be chosen to process

data collections, containing each up to 10

9records. Average processing

time of the packageAisTA(n) = 0.001nmilliseconds and the average processing time of the packageBisTB(n) = 500⎷nmilliseconds. Which algorithm has better performance in a "Big-Oh" sense? Work out exact conditions when these packages outperform each other.

12. Software packagesAandBof complexityO(nlogn) andO(n), respec-

tively, spend exactlyTA(n) =cAnlog10nandTB(n) =cBnmilliseconds to processndata items. During a test, the average time of processing n= 104data items with the packageAandBis 100 milliseconds and 500 milliseconds, respectively. Work out exact conditions when one package actually outperforms the other and recommend the best choice if up to n= 109items should be processed.

13. Let processing time of an algorithm of Big-Oh complexityO(f(n)) be

directly proportional tof(n). Let three such algorithmsA,B, andC have time complexityO(n2),O(n1.5), andO(nlogn), respectively. During a test, each algorithm spends 10 seconds to process 100 data items. Derive the time each algorithm should spend to process 10,000 items.

14. Software packagesAandBhave processing time exactlyTEP= 3n1.5and

T WP= 0.03n1.75, respectively. If you are interested in faster processing of up ton= 108data items, then which package should be choose?

1.2 Time complexity and Big-Oh notation: solutions

1. 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 appropriate base can be used in the above formula (say, base of 10). Therefore, for n= 1000000 the time isT(1,000,000) =T(1,000)·1000000log1010000001000log

101000=

1·1000000·61000·3= 2,000 ms

2. The constant factorc=T(N)N

2, thereforeT(n) =T(N)n2N

2=n210000

ms and

T(5000) = 2,500 ms.

3. The constant factorc=T(1000)f(1000)=10f(1000)milliseconds per item. There-

fore,T(n) = 10f(n)f(1000)ms andT(100,000) = 10f(100,000)f(1000)ms. Iff(n) =n thenT(100,000) = 1000 ms. Iff(n) =n3, thenT(100,000) = 107ms. 3

4.ExpressionDominant term(s)O(...)5 + 0.001n3+ 0.025n0.001n3O(n3)500n+ 100n1.5+ 50nlog10n100n1.5O(n1.5)0.3n+ 5n1.5+ 2.5·n1.752.5n1.75O(n1.75)n

2log2n+n(log2n)2n

8n+ log2log2log2n3log

8nO(logn)100n+ 0.01n20.01n2O(n2)0.01n+ 100n2100n2O(n2)2n+n0.5+ 0.5n1.250.5n1.25O(n1.25)0.01nlog2n+n(log2n)2n(log2n)2O(n(logn)2)100nlog3n+n3+ 100nn

3O(n3)0.003log4n+ log2log2n0.003log4nO(logn)5.StatementIs it TRUE

or FALSE?If it is FALSE then write the 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)TRUE

Transitivity:

ifg=O(f) andh=O(f) theng=O(h)FALSEifg=O(f) and f=O(h) then g=O(h)5n+8n2+100n3=O(n4)TRUE

5n+ 8n2+ 100n3=

7. In the Big-Oh sense, the algorithmBis better. It outperforms the algo-

4 inequality reduces to log algorithm of choice isA.

8. The constant factors forAandBare:

c

A=101024log

21024=11024

;cB=11024 2

Thus, to process 2

20= 10242items the algorithmsAandBwill spend

T

A(220) =11024

220log2(220) = 20280μs andTB(220) =11024

2240= 220μs,

respectively. BecauseTB(220)?TA(220), the method of choice isA.

9. In the Big-Oh sense, the algorithmBis better. It outperforms the algo-

n≥100,000.

10. In the "Big-Oh" sense, the algorithmBof complexityO(n) is better than

Aof complexityO(nlogn). he packageBhas better performance in a The packageBbegins to outperformAwhen (TA(n)≥TB(n), that is, when 0.1nlog2n≥5·n. This inequality reduces to 0.1log2n≥5, or n≥250≈1015. Thus for processing up to 1012data items, the package of choice isA.

11. In the "Big-Oh" sense, the packageBof complexityO(n0.5) is better

thanAof complexityO(n). The packageBbegins to outperformAwhen (TA(n)≥TB(n), that is, when 0.001n≥500⎷n. This inequality reduces to⎷n≥5·105, orn≥25·1010. Thus for processing up to 109data items, the package of choice isA.

12. In the "Big-Oh" sense, the packageBof linear complexityO(n) is better

than the packageAofO(nlogn) complexity. The processing times of the packages areTA(n) =cAnlog10nandTB(n) =cBn, respectively. The tests allows us to derive the constant factors: c

A=10010

4log10104=1400

c

B=50010

4=120 The packageBbegins to outperformAwhen we must estimate the data sizen0that ensuresTA(n)≥TB(n), that is, whennlog10n400 ≥n20 . This inequality reduces to log

10n≥40020

, orn≥1020. Thus for processing up to 10

9data items, the package of choice isA.

13.ComplexityTime to process 10,000 items

A1O(n2)T(10,000) =T(100)·100002100

2= 10·10000 = 100,000 sec.A2O(n1.5)T(10,000) =T(100)·100001.5100

1.5= 10·1000 = 10,000 sec.A3O(nlogn)T(10,000) =T(100)·10000log 10000100log 100

= 10·200 = 2,000 sec.5

14. In the Big-Oh sense, the packageAis better. But it outperforms the

equality reduces ton0.25≥3/0.03(= 100), orn≥108. Thus for processing up to 10

8data items, the package of choice isB.

1.3 Recurrences and divide-and-conquer paradigm: exer-

cises

1. Running timeT(n) of processingndata items with a given algorithm is

described by the recurrence:

T(n) =k·T?nk

+c·n;T(1) = 0. Derive a closed form formula forT(n) in terms ofc,n, andk. What is the computational complexity of this algorithm in a "Big-Oh" sense?Hint: To have the well-defined recurrence, assume thatn=kmwith the integer m= logknandk.

2. Running timeT(n) of processingndata items with another, slightly dif-

ferent algorithm is described by the recurrence:

T(n) =k·T?nk

+c·k·n;T(1) = 0. Derive a closed form formula forT(n) in terms ofc,n, andkand detemine computational complexity of this algorithm in a "Big-Oh" sense.Hint: To have the well-defined recurrence, assume thatn=kmwith the integer m= logknandk.

3. What value ofk= 2, 3, or 4 results in the fastest processing with the

above algorithm?Hint: You may need a relation logkn=lnnlnkwhere ln denotes the natural logarithm with the basee= 2.71828...).

4. Derive the recurrence that describes processing timeT(n) of the recursive

method: public static int recurrentMethod( int[] a, int low, int high, int goal ) { int target = arrangeTarget( a, low, high ); if ( goal < target ) return recurrentMethod( a, low, target-1, goal ); else if ( goal > target ) return recurrentMethod( a, target+1, high, goal ); else return a[ target ]; 6 A non-recursive methodarrangeTarget()has linear time complexity T(n) =c·nwheren=high-low+ 1 and returns integertargetin are equiprobable in this range, e.g. iflow= 0 andhigh=n-1, then everytarget= 0,1,...,n-1 occurs with the same probability1n . Time for performing elementary operations like if-else or return should not be taken into account in the recurrence. Hint: consider a call ofrecurrentMethod()forn=a.lengthdata items, e.g.recurrentMethod( a, 0, a.length - 1, goal )and analyse all recurrences forT(n) for different input arrays. Each recurrence involves the number of data items the method recursively calls to.

5. Derive an explicit (closed-form) formula for timeT(n) of processing an

array of sizenifT(n) is specified implicitly by the recurrence:

T(n) =1n

(T(0) +T(1) +···+T(n-1)) +c·n;T(0) = 0 Hint: You might need then-th harmonic numberHn= 1+12 +13 +···+1n lnn+ 0.577 for deriving the explicit formula forT(n).

6. Determine an explicit formula for the timeT(n) of processing an array of

sizenifT(n) relates to the average ofT(n-1), ...,T(0) as follows:

T(n) =2n

(T(0) +···+T(n-1)) +c where T(0) = 0. Hint: You might need the equation11·2+12·3+···+1n(n+1)=nn+1for deriving the explicit formula forT(n).

7. The obvious linear algorithm for exponentiationxnusesn-1 multiplica-

tions. Propose a faster algorithm and find its Big-Oh complexity in the case whenn= 2mby writing and solving a recurrence formula.

1.4 Recurrences and divide-and-conquer paradigm: solu-

tions

1. The closed-form formula can be derived either by "telescoping"

1or by

guessing from a few values and using then math induction.1 If you know difference equations in math, you will easily notice that the recurrences are the difference equations and "telescoping" is their solution by substitution of the same equation for gradually decreasing arguments:n-1 orn/k. 7 (a)Derivation with "telescoping":the recurrenceT(km) =k·T(km-1) + c·kmcan be represented and "telescoped" as follows:

T(km)k

m=T(km-1)k m-1+c

T(km-1)k

m-1=T(km-2)k m-2+c T(k)k =T(1)1 +c

Therefore,

T(km)k

m=c·m, orT(km) =c·km·m, orT(n) =c·n·logkn.

The Big-Oh complexity isO(nlogn).

(b)Another version of telescoping:the like substitution can be applied directly to the initial recurrence:

T(km) =k·T(km-1) +c·km

k·T(km-1) =k2·T(km-2) +c·km k m-1·T(k) =km·T(1) +c·kmso thatT(km) =c·m·km (c)Guessing and math induction:let us construct a few initial values ofT(n), starting from the givenT(1) and successively applying the recurrence:

T(1) = 0

T(k) =k·T(1) +c·k=c·k

T(k2) =k·T(k) +c·k2= 2·c·k2

T(k3) =k·T(k2) +c·k3= 3·c·k3

This sequence leads to an assumption thatT(km) =c·m·km. Let us explore it with math induction. The inductive steps are as follows: (i) The base caseT(1)≡T(k0) =c·0·k0= 0 holds under our assumption. (ii) Let the assumption holds forl= 0,...,m-1. Then

T(km) =k·T(km-1) +c·km

=k·c·(m-1)·km-1+c·km =c·(m-1 + 1)·km=c·m·km Therefore, the assumed relationship holds for all valuesm= 0,1,...,∞, so thatT(n) =c·n·logkn. 8 The Big-Oh complexity of this algorithm isO(nlogn).

2. The recurrenceT(km) =k·T(km-1) +c·km+1telescopes as follows:

T(km)k

m+1=T(km-1)k m+c

T(km-1)k

m=T(km-2)k m-1+c T(k)k

2=T(1)k

+c

Therefore,

T(km)k

m+1=c·m, orT(km) =c·km+1·m, orT(n) =c·k·n·logkn.

The complexity isO(nlogn) becausekis constant.

3. Processing timeT(n) =c·k·n·logkncan be easily rewritten asT(n) =

c klnk·n·lnnto give an explicit dependence ofk. Because2ln2 = 2.8854, 3ln3 = 2.7307, and4ln4 = 2.8854, the fastest processing is obtained for k= 3.

4. Because all the variants:

T(n) =T(0) +cnorT(n) =T(n-1) +cniftarget= 0

T(n) =T(1) +cnorT(n) =T(n-2) +cniftarget= 1

T(n) =T(2) +cnorT(n) =T(n-3) +cniftarget= 2

T(n) =T(n-1) +cnorT(n) =T(0) +cniftarget=n-1

are equiprobable, then the recurrence is

T(n) =1n

(T(0) +...+T(n-1)) +c·n

5. The recurrence suggests thatnT(n) =T(0)+T(1)+···+T(n-2)+T(n-

1)+cn2. It follows that (n-1)T(n-1) =T(0)+...+T(n-2)+c·(n-1)2,

and by subtracting the latter equation from the former one, we obtain the following basic recurrence:nT(n)-(n-1)T(n-1) =T(n-1)+2cn-c. It reduces tonT(n) =n·T(n-1)+2cn-c, orT(n) =T(n-1)+2c-cn Telescoping results in the following system of equalities:

T(n) =T(n-1) +2c-cn

T(n-1) =T(n-2) +2c-cn-1··· ··· ··· ··· ···

T(2) =T(1) +2c-c2

T(1) =T(0) +2c-c

BecauseT(0) = 0, the explicit expression forT(n) is:

T(n) = 2cn-c·?

1 +12 +···+1n = 2cn-Hn≡2cn-lnn-0.577 9

6. The recurrence suggests thatnT(n) = 2(T(0)+T(1)+...+T(n-2)+T(n-

1))+c·n. Because (n-1)T(n-1) = 2(T(0)+...+T(n-2))+c·(n-1),

the subtraction of the latter equality from the former one results in the following basic recurrencenT(n)-(n-1)T(n-1) = 2T(n-1) +c. It reduces tonT(n) = (n+ 1)T(n-1) +c, orT(n)n+1=T(n-1)n +cn(n+1). Telescoping results in the following system of equalities:

T(n)n+1=T(n-1)n

+cn(n+1)T(n-1)n =T(n-2)n-1+c(n-1)n T(2)3 =T(1)2 +c2·3T(1)2 =T(0)1 +c1·2 BecauseT(0) = 0, the explicit expression forT(n) is: T(n)n+ 1=11·2+c2·3+···1(n-1)n+cn(n+ 1)=c·nn+ 1 so thatT(n) =c·n. An alternative approach (guessing and math induction):

T(0) = 0

T(1) =21

·0 +c=c

T(2) =22

(0 +c) +c= 2c

T(3) =23

(0 +c+ 2c) +c= 3c

T(4) =24

(0 +c+ 2c+ 3c) +c= 4c It suggests an assumptionT(n) =cnto be explored with math induction: (i) The assumption is valid forT(0) = 0. (ii) Let it be valid fork= 1,...,n-1, that is,T(k) =kcfork=

1,...,n-1. Then

T(n) =2n

(0 +c+ 2c+...+ (n-1)c) +c 2n (n-1)n2 c+c = (n-1)c+c=cn

The assumption is proven, andT(n) =cn.

quotesdbs_dbs24.pdfusesText_30

[PDF] la composante vivante dun milieu naturel

[PDF] les composantes de lenvironnement 6ème

[PDF] quelles sont les composantes de lenvironnement

[PDF] les composantes de l'environnement svt 6ème

[PDF] les composantes dun milieu naturel

[PDF] quelles sont les composantes dun milieu naturel

[PDF] les elements qui composent l'environnement

[PDF] les composantes de lenvironnement pdf

[PDF] 1.1.1 tenue des dossiers fournisseurs et sous-traitants

[PDF] 1.1.4 evaluation et suivi des stocks

[PDF] 1.2.3 traitement des devis des commandes

[PDF] 1.2.4 traitement des livraisons et de la facturation

[PDF] 1.3.1 suivi de la trésorerie et des relations avec les banques

[PDF] tenue des dossiers clients donneurs d ordre et usagers

[PDF] 2.2.3 suivi administratif des carrières