Prashnikaप्रश्निका
Code
About
‹ 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).