Question

Question 1. (1 marks) The following procedure has an input array A[1..n] with n > 2 arbitrary integers. In the pseudo-code, "return” means immediately erit the procedure and then halt. Note that the indices of array A starts at 1. NOTHING(A) 1 n = A. size 2 for i = 1 ton // i=1,2,..., n (including n) 3 for j = 1 ton // j = 1,2,...,n (including n) 4. if A[n - j +1] + j then return 5 if (A[i] + n-i) or (A[1] + A[2] = 2n-3) then return 6 return Assume that each assignment, comparison and arithmetic operation takes constant time. Let T(n) be the worst-case time complexity of calling NOTHING(A) on an array A of size n > 2. Give a tight asymptotic bound for T(n), that is give a function f(n) such that T(n) is (f(n)). Justify your answer by explaining why it is (f(n)), and why it is 2(f(n)). Any answer without a sound and clear justification may receive no credit.

Answer 1

Since here we have to calculate T(n) as worst case time complexity . To calculate worst case time complexity

let's assume that for all i and j , both 'if' statements given in program is False because otherwise function will be returned to main function and we might not get worst case for T(n) .

We will Calculate time complexity line by line

1. n = A.size ( This line will take constant time lets O(1) because it is just an arithmetic operation.)

time complexity for any for loop is number of time inner statement is executed.

2. for i=1 to n

3. for j=1 to n

4. if A[n-j+1] != j then return (this line is a inner statement for both for loops)

5. if (A[i]!=n-i) or (A[1]+A[2] = 2*n-3) then return ( this line is also a statement)

in case of nested for loops time complexity is number of times inner statement is executed.

here for every value of i , for loop of line 3 executes from j=1 to n means 'n' number of times.

Therefore number of times inner loop executes is = (n+n+n......('n' times)) = n(1+1+1+.....n times) = n ²

Therefore for line 2,3,4,5 total time complexity will be O(n ²)

so total time complexity T(n) = O(n ²) + C = O(n ²)

Now question is why it is O(n ²) and not Ω(n ²) that is because our upper bound is n² and we will never execute

both nested for loops greater than n² times .

Therefore Your Answer is O(n ²).