Consider the following pseudocode fragment. 1: function stars(n) 2: for i ? 1; i ? n; i++ do 3: Print '*' i times

a) Using the O-notation, upperbound the running time of stars.

b) Using the ?-notation, lowerbound the running time of stars to show that your upperbound is in fact asymptotically tight.

Transcribed Image Text:

Solution 3. a) The first iteration prints 1 star, second prints two, third prints three and so on. The total number of stars is 1+ 2+ + n, namely, n j n=n = 0(n). j=1 j=1 n 1 Solution 1: Analysis b) Assume for simplicity that n is even. To lowerbound the running time, we consider only the number of stars printed during the last iterations. Since this is part of the full execution, analyzing only this part gives a lower bound on the total running time. The main observation we need is that for each of the considered iterations, we print at least n/2 stars, allowing us to lower bound the total number of stars printed: n n ;> j=n/2+1 n 2 = = Q(n). Solution 3. a) The first iteration prints 1 star, second prints two, third prints three and so on. The total number of stars is 1+ 2+ + n, namely, n j n=n = 0(n). j=1 j=1 n 1 Solution 1: Analysis b) Assume for simplicity that n is even. To lowerbound the running time, we consider only the number of stars printed during the last iterations. Since this is part of the full execution, analyzing only this part gives a lower bound on the total running time. The main observation we need is that for each of the considered iterations, we print at least n/2 stars, allowing us to lower bound the total number of stars printed: n n ;> j=n/2+1 n 2 = = Q(n).