CODEWITHSUNDEEP
javatime-complexity
user2899944
user2899944

Reputation: 269

Complexity of java code with nested for loops

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;
      }
   }
}

Upvotes: 2

Views: 139

Answers (2)

Eran
Eran

Reputation: 394026

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.

Upvotes: 2

Ingo
Ingo

Reputation: 36339

The number of loops is controlled by b.length which is a constant and the index variables i and j. As long as you don't meddle with i an j inside the loop, the complexity remains the same.

Upvotes: 1

Related Questions