CODEWITHSUNDEEP
algorithmtime-complexity
Sza2002
Sza2002

Reputation: 1

Calculation time complexity of an algorithm

I'm trying to calculate time complexity of this algorithm but I'm really struggling trying to understand how many times each will execute. I would really appreciate explanation on how to think when doing these exercises not just this one in particular

int SortRight(A, i) {
n= len(A);
if (i == n-1) return A;
for (j= (i + 1); j < n; j++) {
if (A[i] < A[j]) { temp= A[i]; A[i]= A[j]; A[j]= temp; } }
  return SortRight(A, i+1)
}

the comments are how many time I think the lines execute but I'm pretty sure this is wrong

int SortRight(A, i) { //n+1
n= len(A); //n+1
if (i == n-1) //n+1
{return A;} /1
for (j= (i + 1); j < n; j++) { // (1) n*(n-1)
if (A[i] < A[j]) { temp= A[i]; A[i]= A[j]; A[j]= temp; } } // i have no idea for this part 
  return SortRight(A, i+1)
}

(1) Assume at one point j>=n so that would be when i=k so j=k+1 => k+1=n k=n-1, (n-1) times the number of times that the rec. call will execute ->n => n*(n-1)

Upvotes: 0

Views: 133

Answers (1)

user1196549
user1196549

Reputation:

Rewrite with the constant-time operations replaced by "Cst" (every Cst is different):

int SortRight(A, i) {
Cst;
if (i == n-1)
  Cst;
else
  for (j= (i + 1); j < n; j++) { Cst; }

return SortRight(A, i+1); }

Now rewrite, replacing all operations by by the time they take:

S(i)= (
  a +
  if (i == n-1)
    b
  else
    (n - i - 1) * c
  + S(i+1))

This is a first-order recurrence, which we put in a more usual form:

S(n-1) = a + b
S(i) = S(i+1) + a + (n - i - 1) * c

We can solve iteratively,

S(n-1) = a + b
S(n-2) = S(n-1) + a + (n - (n - 2) - 1) c = 2a + b + c
S(n-3) = S(n-2) + a + (n - (n - 3) - 1) c = 3a + b + 3c
S(n-4) = S(n-3) + a + (n - (n - 4) - 1) c = 4a + b + 6c
....

You can check that the respective coefficients are n-1-i, 1, T[n-1-i], where T denotes a triangular number. In particular,

S(0) = (n-1).a + b + T[n-1].c

Advanced note:

In fact, the body of the loop does not take constant time: it can be the time for just a comparison, say c' or a comparison and a swap, c' + c". The respective counts depends on the initial ordering of the array, which we don't know. Anyway we can write

S(0) = (n-1).a + b + T[n-1].c' + N(A).c"

where N(A) denotes the number of swaps performed, which is also the initial number of inversions in the array.

Upvotes: 1

Related Questions