Can someone confirm me that the complexity of this algorithm is O(n^2)?
a = 0
b = 0
c = n
while (b <= c)
{
for (j = b; j<=c; j++)
{
a = j * j -2 * j + 3
}
b = b + 3
c = c + 2
}
The inner loop executes c - b + 1 times. Each execution of the inner loop body a = j * j -2 * j + 3 takes constant (bounded) time (assuming we're dealing with fixed-width integer types, otherwise it would depend on the multiplication algorithm used [and addition, but that's hard to implement in a way that multiplication is faster]), so the execution of the body of the outer loop is O(d) (Θ(d) even), where d = c - b + 1.
The updates of the variables controlling the outer loop
b = b + 3
c = c + 2
decrease the difference c - b by 1 in each execution of the outer loop's body, hence the outer loop is executed n+1 times, and you have a total of O(n²), since
n n+1
∑ (n+2k - (3k) +1) = ∑ j = (n+1)(n+2)/2
k=0 j=1
It even is Θ(n²), unless the compiler optimises and sets all variables to their final values directly.
Answer for original question with typo:
The inner loop
for (j = b; j==c; j++)
will execute either once - when b == c or not at all, so the body of the outer loop is O(1). The updates in the outer loop
b = b + 3
c = c + 2
mean that the difference c-b decreases by 1 each time the loop body is executed, so
b = 0
c = n
while (b <= c)
will execute n+1 times - total: O(n).