In the following procedure, the input is an array A[1.n] of arbitrary integers, A.

In the following procedure, the input is an array A[1..n] of arbitrary integers, A.size is a variable containing the size n of the array A (assume that A contains at least n > 2 elements), and “return” means return from the procedure call.

0. Procedure nothing(A)

1. A[1] := 0

2. A[2] := 1

3. for i = 3 to A.size do

4.       s := 0

5.       for j = 1 to i-1 do s := s + A[j]

6.       if A[i] is not equal to s then return

7. return

QU. Let T(n) be the worst-case time complexity of executing procedure nothing() on an array A of size n > 2. Assume that assignments, comparisons and arithmetic operations, like additions, take a constant amount of time each.

State whether T(n) is Ω(n2) and justify your answer.

It is worth 12 marks and therefore is not trivial.

As we have to analyse the algorithm in worst case we assume that the condition of ifstatement that is A[i]==s is always true so that both loop can run up to maximum number oftimes.The algorithm...