‹ Back to the paper
Question 1(ix)
1 mark
Computer ScienceISC 2025 Specimen Computer Science Paper 1Short answerComplexity and Big O notation
Answer the following.
For Big O notation, state the difference between O(n) and O(n²).
For Big O notation, state the difference between $O(n)$ and $O(n^2)$.
Answer
Answer
Official answer key$O(n)$ denotes linear time complexity, where the running time grows directly in proportion to the input size $n$; it is typically produced by a single loop that runs $n$ times. $O(n^2)$ denotes quadratic time complexity, where the running time grows in proportion to the square of $n$; it is typically produced by a nested loop (a loop inside a loop), and so it grows far faster than $O(n)$ as $n$ increases.