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