CODEWITHSUNDEEP
algorithmasymptotic-complexitybig-o
user7716543
user7716543

Reputation:

Algorithm asymptotic-complexity

I would like to know what is the minimum and maximum value this procedure can return in the following algorithm using the big-theta notation. The algorithm is:

procedure F(𝐴[1..n])
   s = 0
   for i = 1 to n
      j = min(max(i,A[i]),n³) 
      s = s + j
   return s

Upvotes: 2

Views: 145

Answers (1)

Patrick87
Patrick87

Reputation: 28332

EDIT: removed original answer as it was for the wrong question.

The analysis hinges on the following line:

min(max(i,A[i]),n³)

If we figure out the cases for this then we can easily figure the cases for the result. We must answer whether i > A[i] and then whether the greater of i and A[i] is greater than n^3.

  1. i > A[i] and i > n^3. This cannot be the case because i <= n and i, n are integers.
  2. i > A[i] and i < n^3. This can happen if, e.g., A[i] = -1. In this case, we are adding i together for 0 <= i <= n. This comes out as n(n+1)/2, which is O(n^2). (I am using O but Theta applies as well).
  3. i < A[i] and A[i] < n^3. This can happen if i + 1<= A[i] <= n^3 - 1 and n > 2. In this case, we are adding i + 1 together n times, for i equal 1 to n, or we are adding n^3 - 1 together n times. On the low end we get n(n-1)/2 - n, as before with the -n term for the -1, and on the high end we get n^4 - n; somewhere between O(n^2) and O(n^4).
  4. i < A[i] and A[i] > n^3. This can happen if A[i] > n^3. In this case we have n^3 summed n times for n^4, O(n^4).

Based on the above, my thinking is that the lower bound on the best case is Omega(n^2) and the upper bound on the worst case is O(n^4). Both of these bounds are tight for their respective cases, but since they are not the same we cannot give a single tight bound for the rate of growth of the result.

Upvotes: 1

Related Questions