in Algorithms
97 views
0 votes
0 votes

1 question:

a) Calculate the running time of the following iterative algorithm. For this purpose, write the working time of each row in the corresponding column of the table in terms of ci coefficients. Write the number of reruns of each row in the corresponding column of the table. Multiply and add the expressions in the row. Calculate the total running time by showing the intermediate steps and write it asymptotically with the notation ϴ.

b) Is it possible to talk about the best, average and worst running times for this algorithm? Why?

c) Code this algorithm with a programming language you know. In particular, j = 1; and j = j * 2; Find the number of times the rows where transactions are made are executed, using a separate counter for each. Take n as a parameter from outside or enter from the keyboard. When you compile and run the program, print the last values ​​of the two counters on the screen. For the values ​​of 5, 10, 15, 20, 25, 30, 35, 40 of the parameter n, plot how many times both lines are executed as a graph.

d) Comment on the similarity/difference between the asymptotic notation you found in option a and the graph in option c.

 

 

pseudo code

Ci

The number of repetitions

ci × Number of repetitions

for i=1 to n

 

 

 

do

 

 

 

j=1;

 

 

 

While (j<n)

 

 

 

do

 

 

 

j=j*2;

 

 

 

                         

                                                Total:

 

T(n)=

 

           

 

in Algorithms
by
97 views

Please log in or register to answer this question.