Question

1. [10 marks] consider the following pseudocode:

   p := 0
   x := 2fori:= 2ton

   p := (p + i ) * x

   a) How many addition(s) and multiplication(s) are performed by the above pseudocode?b) Express the time-complexity of the pseudocode using the big-Θ notation.) Trace the algorithm, below, then answer (c) and (d):   Procedure xyz(n: integer) s := 0, for i:= 1 to n, for j:= 1to i, s:= s+ j*(i− j+ 1) return s

c) What is the time-complexity for the algorithm xyz? d) Express the number of operations carried out by the algorithm using the summation notation

Answer 1

Solution:

(a)

Explanation:

=>We can see that in the given code loop is running from i = 2 to i = n means total number of times loop is executed = n-1 times.

=>For each iteration of for loop statement p := (p+i)*x is executed and the statement includes one addition and one multiplication.

=>Hence total number of additions = n-1 additions

=>Total number of multiplications = n-1 multiplications

(b)

Explanation:

=>As there is only one for loop and which is running n-1 times so time complexity = $\Theta$ (n)

(c)

Explanation:

=>In xyz algorithm we can see that there are two for loops.

=>Outer for loop is independent and will run n times from i = 1 to i = n incrementing value of i by 1 each time.

=>Inner for loop is dependent for loop and will run from j = 1 to j = i incrementing the value of j by 1 each time.

=>When i = 1 inner loop will executed only once for j = 1, when i = 2 inner loop will run twice for j = 1, 2 and so on.

=>Total number of times loops will be executed = 1 + 2 + 3 + .. + n

=>Total number of times loops will be executed = n(n+1)/2

=>Hence time complexity = O(n^2)

(d)

Explanation:

=>Let say the cost of calcualting s := s + j*(i-j+1) = C where C is some constant.

=>We can write the number of operations using summation operations = $\sum$ (i = 1 to i = n)$\sum$(j = 1 to j = i) (C)

I have explained each and every part with the help of statements attached to it.