mercredi 23 juin 2021

How to formulate the exact cost of operations for this recursive function?

I'm asked to count the exact number of operations cost for this function. I've used op to keep track of it. The recursive call should be the number of operations performed by that function call (I'm not sure if I'm doing that right in my code). My question is, how do I formulate a mathematical equation to match the number of operations. I've commented beside each line to annotate the cost of operations. From that, i get 2n^2 - n + 6. But this don't match with my output.

// PARAM: arr is array to be sorted, n is size of array, i should initially = 0
int ssort(int arr[], int n, int i)
{
       int op = 0;
       if (i < n-1)            //1
       {
              // Find and swap smallest remaining
              int next = i + 1;        //1
              int smallest = i;       //1

              while (next < n)         //i+1
              {
                     if (arr[next] < arr[smallest])     //i
                     {
                          smallest = next;      //i
                     }
                     next++;     //i
                     op += 4; altogether 4 ops
              }
              op++; //while loop terminates

              // Swap i with smallest  
              int temp = arr[i];      //1
              arr[i] = arr[smallest];   //1
              arr[smallest] = temp;    //1
              op += ssort(arr, n, i + 1);
       } 
       op+=6;

       return op;
}

Aucun commentaire:

Enregistrer un commentaire