Numéro 2. (12 pts) Consider the following pseudo-code

function machin (n: natural) return natural

begin

1

2

3

4

5

6

7

8

9

10

11

22449

12

13

14

15

sum - 0

x+0

y +0

for k ← 1 to n do

y+x+y

x+2-1

i+1

while i ≤ 2k do

sum sum +i

for j+1 to k+ i do

sum + sum + j

end for

i+i+2

end while

end for

16 return sum +z-y

end machin

(a) (6 points) Calculate the exact number of assignments + depending on n performed by

the machin function. Don't forget the control variable assignments for each of the loops

for (including the last one to exit the loop). Note that calling machin(4) generates 170

assignments.

Response:

(b) (2 points) Give the number of asymptotic assignments using the notation .

Response :

(e) (4 points) Determine a barometric operation or instruction to evaluate the asymptotic com-

plexity of the function and justify your choice. Give the asymptotic complexity of the function

using your barometric operation.

Response :