Question

The following is the routine PLOOVIN, a critical component of nothing in particular. Derive a recurrence for the time complexity of PLOOVIN, and express that time complexity in Θ-notation. Do not worry about floors and ceilings.

int PLOOVIN(A, left, right) if (right - left < 4) {

return 1; }

int sum = 0;
for(int i=left; i<right; i++) {

for(int j = i+1; j<right; j++) {

sum = sum + A[i] * A[j];

}

sum = sum + A[i];

}

int mid = (left + right) / 2;

int qone = (left + mid) / 2;

int qtwo = (mid + right) / 2;

plooA = PLOOVIN(A, left, mid);

plooB = PLOOVIN(A, qone, two);

plooC = PLOOVIN(A, mid, right);

int min = plooA;

if(plooB < min) {

min = plooB;

}

if(plooC < min) {

min = plooC;

}

return sum - min;

Answer 1

If you like the solution please give it a thumbs up. And if you have any query please let me know in the comments.

Solution :-

Recurrence for time complexty ->

T(n) = T(n/4) + T(n/2) + T(n/4) + n²  = 2.T(n/4) + T(n/2) + n²

Here quadratic term is for nested loops and other T(x) terms for 3 recursive calls.

If we try to solve this recurrence using recursive tree method then there will be two brances, one from T(n/4) and other from T(n/2) term, having approx. heights of log₄N and log₂N . That we can summarize both to the log₂N .

So now time complexity will be in terms of N²logN, where N is size of array A.

Time complexity = Θ(N²logN)