CODEWITHSUNDEEP
algorithmtime-complexity
Matheus Simões Minghini
Matheus Simões Minghini

Reputation: 147

Algorithm complexity notation

I am learning about algorithm complexity and I got a simple algorithm to be analyzed by me, this is the algorithm:

function test(int x, int y, int N){
  int i, j, k;
  if (x==y) {
   for (i = 0; i < N; i++) {
      for (j = 0; j < N; j++) {
        commands here
      }
   }
   for (i = 0; i < N; i++) {
     commands here
   }
  }else {
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
           for (k = 0; k < N; k++) {
              commands here
           }
       }
    }
  }
}

I analyzed as follows:

f( x, y, n) = n² + n (if x = y)

f( x, y, n) = n³ (if x ≠ y)

That means that in the best-case scenario, f(n) = n² + n or simply O(n²) and in the worst-case scenario, f(n) = n³ or simply O(n³)

My question is: Is my understanding correct? Realizing which function is bigger is something intuitive, but do I need to compare both functions mathematically to prove that? On top of that, is the module right?

Thanks, guys!

Upvotes: 1

Views: 52

Answers (1)

J. LaF
J. LaF

Reputation: 127

Assuming 'commands here' are performed in constant-time, then you are correct.

You're describing a piecewise time complexity for this given algorithm, dependent on the values of x and y. You've correctly broken down the two cases and analyzed their complexity, again assuming the 'commands' are constant-time. Now to compare the two cases more rigorously:

Showing that latter case, (x!=y), is asymptotically larger than the former, (x==y), and thus is the worst-case, is as simple as showing that N^3 is at least as large as N^2 for all values of N greater than a certain value. Since N^3 is greater than N^2 for all values at least 0, we can say that N^2 = O(N^3) and thus O(N^3) is in fact the worse of the two cases and thus the worst-case runtime. A symmetric argument can be applied to show the other case is then the best-case runtime.

You can show the same thing quicker by taking the limit of one runtime divided by the other as N goes to infinity. If that limit goes to 0, then the numerator = O(denominator), and if it goes to infinity then the reverse is true. If it goes to some positive constant then the two have the same asymptotic complexity, expressed by the omega notation.

brief review of asymptotic notation

You could dive into average-case analysis if you knew anything about the distributions of X and Y, since you would be able to determine the probability that the worst/best case occur.

Upvotes: 3

Related Questions