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)=
|
|
| |
|
|
|
|
|
