So I was given this algorithm to compute the efficieny in which I found sorts an array into ascending order.

    for i = 1 to n-1 do   //n
       minJ = i           //n-1
       minX = T[i]        //n-1
       for j = i+1 to n do  //sum_{i=1}^{n} t
          if T[j] < minX then ** //sum_{i=1}^{n} t-1
             minJ = j             //sum_{i=1}^{n} t-1
             minX = T[j]         ////sum_{i=1}^{n} t-1
      T[minJ] = T[i]      //n-1
      T[i] = minX         //n-1

I also listed the number of times the line of code is run. I need to find the efficiency and how many time the line at ** is calculated. Any help is appreciated thank you.

  • 2
    $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Nov 3 '16 at 8:47
  • $\begingroup$ To calculate the efficiency you have to do it, in terms of the worst case possible. One loop will traverse the array at least n times. And it seems, you have two loops so this means your operations will be N * N which is N^2 on a worst case scenario. $\endgroup$ – Juniar Nov 3 '16 at 13:36

The best way (The way I was taught at least) is to look for a basic operation. That's the operation that most significantly impacts the performance of an algorithm. In your case it looks like if T[j] < minX then would be your basic operation as it's performed the most times, where the statements inside of the if check are only performed if the condition is true. The fact you have two for loops going from 1 to n-1 tell me that you're working with quadratic time. You're going to be doing your basic operation at minimum n^2 or n operations n times. This should tell you that your algorithm performs in O(n^2) timing.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.