Question

1. Exercise 3.7 of the textbook.

An algorithm prints the following pattern:

*

* *

* * *

* * * *

* * * * *

A. What are the basic operations performed by the algorithm that you would count towards its running time?

B. Count the number of these basic operations for the specific output shown above.

C. The number of lines printed in the preceding pattern is 5. Assume that the algorithm can extend this pattern for any number of lines (line number i has i stars). If the number of lines, n is the input to the algorithm, how many basic operations are performed as a function of n?

D. Write your answer to the above question as a big O order.

Answer 1

A. The very basic operations performed by the algorithm that one would count towards its running time is NUMBER OF STARS PRINTED , NUMBER OF BLANKSPACE (BETWEEN EACH STAR) , NEWLINE . These all basic operations can be easily controlled by any loop (for loop is most appropiate).

B. there are 15 stars , 10 blankspace and 5 newlines .

c. If there is n as the number of lines given input then , Number of starts will be n.(n+1)/2 , it is nothing but sum of n numbers given as input ,

Numbers of blankspace will be n.(n-1)/2 , it is the sum of (n-1) number therfore each line will have one less blankspace as the line number(i.e line no 2 will have 1 blankspace and so on) .

Number of newline will be n ,i.e the number given as input .

D. O(n²) this is generally used for nested loop and hence here also nested loop is used therefore this will be the bigO order for the algorithm

As a BIg O order the above algorithm will be having O(n²) which is directly proportional to the size of the given input.