‹ Back to the paper
Question 1(x)
1 mark
Computer ScienceISC 2025 Improvement Computer Science Paper 1Short answerComplexity and Big O notation
Answer the following.
For the given code segment, write Big O notation for worst case complexity. int i=1, j=1, k=1, p…
For the given code segment, write Big O notation for worst case complexity.
int i=1, j=1, k=1, p;
while (i <= p)
{
statements
}
while (j <= p)
{
while (k <= p)
{
statements
}
}Answer
Answer
Checked answer.
$O(n^2)$
The first loop runs $n$ times, giving $O(n)$. The second part is a nested pair of loops: the outer loop runs $n$ times and, for each of its passes, the inner loop runs $n$ times, giving $n \times n$ steps, i.e. $O(n^2)$. Adding the two, $O(n) + O(n^2) = O(n^2)$, because the $n^2$ term dominates. Worst case time complexity = $O(n^2)$ (quadratic).