1.1 Time complexity and Big-Oh notation: exercises

157_3220exercises1.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

the other. If your problems are of the sizen≤109, which algorithm will 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

2log2nO(n2logn)nlog3n+nlog2nnlog3n,nlog2nO(nlogn)3log

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=

O(n2logn)FALSE5n+8n2+100n3=O(n3)6. 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-

4 rithmAwhenTB(n)≤TA(n), that is, when 2.5n2≤0.1n2log10n. This inequality reduces to log

10n≥25, orn≥n0= 1025. Ifn≤109, the

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-

rithmAifTB(n)≤TA(n), that is, if 25n≤5nlog10n, or log10n≥5, or 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

packageBwhenTA(n)≤TB(n), that is, when 3n1.5≤0.03n1.75. This in- 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 The range of input variables is 0≤low≤goal≤high≤a.length-1. A non-recursive methodarrangeTarget()has linear time complexity T(n) =c·nwheren=high-low+ 1 and returns integertargetin the rangelow≤target≤high. Output values ofarrangeTarget() 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.

7. A straightforward linear exponentiation needs

n2 = 2m-1multiplications to producexnafter having alreadyxn2 . But becausexn=xn2

·xn2

, it can be computed with only one multiplication more than to computexn2 . Therefore, more efficient exponentiation is performed as follows:x2=x·x, x

4=x2·x2,x8=x4·x4, etc. Processing time for such more efficient

10 algorithm corresponds to a recurrence:T(2m) =T(2m-1) + 1, and by telescoping one obtains:

T(2m) =T(2m-1) + 1

T(2m-1) =T(2m-2) + 1

··· ···

T(2) =T(1) + 1

T(1) = 0

that is,T(2m) =m, orT(n) = log2n. The "Big-Oh" complexity of such algorithm isO(logn).

1.5 Time complexity of code: exercises

1. Work out the computational complexity of the following piece of code:

for( int i = n; i > 0; i /= 2 ) { for( int j = 1; j < n; j *= 2 ) { for( int k = 0; k < n; k += 2 ) { ... // constant number of operations } } }

2. Work out the computational complexity of the following piece of code.

for ( i=1; i < n; i *= 2 ) { for ( j = n; j > 0; j /= 2 ) { for ( k = j; k < n; k += 2 ) { sum += (i + j * k ); } } }

3. Work out the computational complexity of the following piece of code

assuming thatn= 2m: for( int i = n; i > 0; i-- ) { for( int j = 1; j < n; j *= 2 ) { for( int k = 0; k < j; k++ ) { ... // constant number C of operations } } } 11

4. Work out the computational complexity (in the "Big-Oh" sense) of the

following piece of code and explain how you derived it using the basic features of the "Big-Oh" notation: for( int bound = 1; bound <= n; bound *= 2 ) { for( int i = 0; i < bound; i++ ) { for( int j = 0; j < n; j += 2 ) { ... // constant number of operations } for( int j = 1; j < n; j *= 2 ) { ... // constant number of operations } } }

5. Determine the average processing timeT(n) of the recursive algorithm:

1 int myTest( int n ) {

2 if ( n <= 0 ) return 0;

3 else {

4 int i = random( n - 1 );

5 return myTest( i ) + myTest( n - 1 - i );

6 } 7 } providing the algorithmrandom( int n )spends one time unit to return a random integer value uniformly distributed in the range [0,n] whereas all other instructions spend a negligibly small time (e.g.,T(0) = 0). Hints: derive and solve the basic recurrence relatingT(n) in average to T(n-1), ...,T(0). You might need the equation11·2+12·3+···+1n(n+1)= nn+1for deriving the explicit formula forT(n).

6. Assume that the arrayacontainsnvalues, that the methodrandomValue

takes constant numbercof computational steps to produce each output value, and that the methodgoodSorttakesnlogncomputational steps to sort the array. Determine the Big-Oh complexity for the following fragments of code taking into account only the above computational steps: for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) a[ j ] = randomValue( i ); goodSort( a ); } 12

1.6 Time complexity of code: solutions

1. In the outerfor-loop, the variableikeeps halving so it goes round log2n

times. For eachi, next loop goes round also log2ntimes, because of dou- bling the variablej. The innermost loop bykgoes roundn2 times. Loops are nested, so the bounds may be multiplied to give that the algorithm is

O?n(logn)2?.

2. Running time of the inner, middle, and outer loop is proportional to

n, logn, and logn, respectively. Thus the overall Big-Oh complexity is

O(n(logn)2).

More detailed optional analysis gives the same value. Letn= 2k. Then the outer loop is executedktimes, the middle loop is executedk+ 1 times, and for each valuej= 2k,2k-1,...,2,1, the inner loop has different execution times:jInner iterations 2 k1 2 k-1(2 k-2k-1)122 k-2(2 k-2k-2)12...... 2 1(2 k-21)122 0(2 k-20)12

In total, the number of inner/middle steps is

1 +k·2k-1-(1 + 2 +...+ 2k-1)12

= 1 +k·2k-1-(2k-1)12 = 1.5 + (k-1)·2k-1≡(log2n-1)n2 =O(nlogn)

Thus, the total complexity isO(n(logn)2).

3. The outerfor-loop goes roundntimes. For eachi, the next loop goes

roundm= log2ntimes, because of doubling the variablej. For eachj, the innermost loop bykgoes roundjtimes, so that the two inner loops together go round 1 + 2 + 4 +...+ 2m-1= 2m-1≈ntimes. Loops are nested, so the bounds may be multiplied to give that the algorithm is

O?n2?.

4. The first and second successive innermost loops haveO(n) andO(logn)

complexity, respectively. Thus, the overall complexity of the innermost part isO(n). The outermost and middle loops have complexityO(logn) andO(n), so a straightforward (and valid) solution is that the overall complexity isO(n2logn). 13 More detailed analysis shows that the outermost and middle loops are interrelated, and the number of repeating the innermost part is as follows:

1 + 2 +...+ 2m= 2m+1-1

wherem=?log2n?is the smallest integer such that 2m+1> n. Thus actually this code has quadratic complexityO(n2). But selection of either answer (O(n2logn) andO(n2) is valid.

5. The algorithm suggests thatT(n) =T(i)+T(n-1-i)+1. By summing

this relationship for all the possible random valuesi= 0,1,...,n-1, we obtain that in averagenT(n) = 2(T(0)+T(1)+...+T(n-2)+T(n-1))+n. Because (n-1)T(n-1) = 2(T(0) +...+T(n-2)) + (n-1), the basic recurrence is as follows:nT(n)-(n-1)T(n-1) = 2T(n-1) + 1, or nT(n) = (n+1)T(n-1)+1, orT(n)n+1=T(n-1)n +1n(n+1). The telescoping results in the following system of expressions:

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

+1n(n+1)T(n-1)n =T(n-2)n-1+1(n-1)n ··· ··· ··· ··· ··· T(2)3 =T(1)2 +12·3T(1)2 =T(0)1 +11·2 BecauseT(0) = 0, the explicit expression forT(n) is: T(n)n+ 1=11·2+12·3+···1(n-1)n+1n(n+ 1)=nn+ 1 so thatT(n) =n.

6. The inner loop has linear complexitycn, but the next called method is

of higher complexitynlogn. Because the outer loop is linear inn, the overall complexity of this piece of code isn2logn. 14