Complexity of java code with nested for loops

user_2899944 0
Viewed 89

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;
      }
   }
}
time-complexity java
2 Answers

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.

user_12215710

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.

user_866040
Related