Question

4 points HunlerDM3 4.5.o04 19 My Notes Let x and n be integers greater than 1. Consider the following algorithm. t0,50 for E 1, 2, ... , x} do for E(1, 2, .., n} do ttx /1ine A L Ss t symbols and the indentation are important: they tell you which lines are inside which loop. So, for example, line A is inside the i-loop, but outside the j-loop The and (a) If x 4 and n 6 initially, what is the value of s after this segment executes? (b) Count the number of additions this segment performs, Your answer should be in terms of x and n

(Please type the answer on computer because I find it difficult to read most of the handwritings!)

Answer 1

j loop increase the value of t by nx as it add x ifor each j and j aply for n times.

Hence for i = 1 the t become nx.

And for i = 2 it becomes 2nx and so on.. So the value of t after the program will be xnx as j loop apply to t for x times.

And for each time after the j loop it adds the value of t to s so the value of s will be nx for i = 1, s = nx + 2nx for i = 2 and so on... So after the program the value of s = nx+2nx+3nx+...+xnx = nx²(x+1)/2

Hence the value of s when x = 4 and n = 6 is 6×4×4×(4+1)/2 = 240.

And the total number of addition is x(n+1) as ofor each i there is n times addition in j loop and 1 addition for s.