Prashnikaप्रश्निका
Code
About
‹ Back to the paper

Question 1(ix)

1 mark

Computer ScienceISC 2025 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. for ( int i=1; i<=P…

For the given code segment, write Big O notation for worst case complexity.
for ( int i=1; i<=P; i++)
{ Statements }
for (int j=1; j<=P; ++j)
    for (int k=1; k<=Q; k++)
    { Statements }

Answer

Answer

Two independent (non-nested) loops each running P times give $O(P)$, and a loop of P nested with a loop of Q gives $O(P \times Q)$. Adding the two, the worst-case complexity is $O(P) + O(P \times Q) = O(P \times Q)$ (the $P \times Q$ term dominates for $P, Q \ge 1$).