Consider the following code segment: for (int x = 1; x <= a; x++) { statements; } for (int y = 1; y…

Computer Science20172 marksOne word

Consider the following code segment:

for (int x = 1; x <= a; x++)
{
    statements;
}
for (int y = 1; y <= b; y++)
{
    for (int z = 1; z <= c; z++)
    {
        statements;
    }
}

(i)[1.0]

What is the worst case complexity of the code segment?

(ii)[1.0]

How would the complexity change if all the three loops went to $N$ instead of $a$, $b$ and $c$?

Answer

$O(a + b \times c)$ The first loop runs a times and the nested loops run b x c times; the two segments are sequential, so their costs add.

$O(N^2)$ With all loops running to N the complexity becomes $O(N + N \times N) = O(N + N^2)$, and the dominant term $N^2$ gives $O(N^2)$.

Complexity and Big O notation