Complexity of java code with nested for loops

user2899944

I am trying to analyze this code below. I wish to calculate both the complexity and the number of operations / iterations (which leads to complexity). My guess is that the complexity is O(n^2), since I have nested for loops. However, inside the inner loop, the values are switching, replacing places. Doesn't this operation makes the algorithm repeat things more than once and hence it's more than O(n^2), or is it only possible with a while loop ? How do I find the exact number of iterations / operations done ?

for (int i = 0; i < b.Length; i++)
{
   for (int j = i + 1; j < b.Length; j++)
   {
       if (b[i] > b[j])
      {
            t = b[i];
            b[i] = b[j];
            b[j] = t;
      }
   }
}
Eran

The outer loop has b.length iterations. Let's call that n.

The inner loop has n - i - 1 iterations.

The total number of iterations of the inner loop is

(n - 1) + (n - 2) + ... + 1 = n * (n -1) / 2 = O(n^2).

Each iteration of the inner loop does constant work - at most 1 condition + 3 assignments - so the total running time is O(n^2).

The exact number of operations depends on the input, since the input determines how many times the condition is true.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related