‹ Back to the paper
Question 2(d)(ii)
1 mark
Computer ScienceISC 2017 Computer Science Paper 1Short answerComplexity and Big O notation
Answer the following question.
How would the complexity change if all the three loops went to N instead of a, b and c?
How would the complexity change if all the three loops went to $N$ instead of $a$, $b$ and $c$?
Show the code
for (int x = 1; x <= a; x++)
{
statements;
}
for (int y = 1; y <= b; y++)
{
for (int z = 1; z <= c; z++)
{
statements;
}
}Answer
Answer
$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)$.