SingaporeComputer ScienceSyllabus dot point

How do we measure and compare the efficiency of algorithms independently of the machine they run on?

Analyse the time and space complexity of an algorithm using Big-O notation, and compare common growth rates

A focused answer to the H2 Computing outcome on algorithmic complexity. Big-O notation, deriving the order of growth from loops and recursion, the common complexity classes, and the trade-off between time and space.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to analyse how an algorithm's running time and memory use grow with the input size, expressed in Big-O notation, and to compare the common growth rates. The central idea is that Big-O describes the order of growth as the input gets large, ignoring machine speed and constant factors, so two algorithms can be compared independently of the hardware.

The answer

What Big-O measures

Big-O notation describes an upper bound on how the cost of an algorithm grows as the input size $n$ grows. It captures the dominant term and drops constants and lower-order terms, because for large $n$ those do not matter:

3n^2 + 5n + 9 \in O(n^2)

We care about $n$ getting large because that is where efficiency differences become decisive.

Reading complexity off code

Count how the number of basic operations scales with $n$ :

A single loop over $n$ items is $O(n)$ .
A loop nested inside another, each over $n$ , is $O(n^2)$ .
Halving the problem each step gives $O(\log n)$ .
Splitting into halves and doing linear work to combine gives $O(n \log n)$ .

# O(n): one pass
for x in data:
    process(x)

# O(n^2): nested passes
for i in data:
    for j in data:
        compare(i, j)

The common complexity classes

From fastest-growing (worst) to slowest-growing (best) for large $n$ :

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

$O(1)$ constant - independent of $n$ .
$O(\log n)$ logarithmic - halving each step (binary search).
$O(n)$ linear - one pass.
$O(n \log n)$ - good comparison sorts (merge sort).
$O(n^2)$ quadratic - nested loops (bubble sort).
$O(2^n)$ exponential - infeasible beyond small $n$ .

Time versus space

Complexity applies to time (operations) and space (extra memory). They often trade off: an algorithm can run faster by using more memory (for example storing precomputed results), or use less memory by recomputing and running slower.

Worked example

Find the Big-O time complexity of this function that checks whether any two elements of a list are equal.

def has_duplicate(data):
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            if data[i] == data[j]:
                return True
    return False

Step 1: Identify the loops

There are two nested loops over the list of length $n$ .

Step 2: Count the inner iterations

For the outer index $i$ , the inner loop runs about $n - i - 1$ times. Summing over all $i$ gives roughly $\dfrac{n(n-1)}{2}$ comparisons.

Step 3: Drop constants and lower terms

$\dfrac{n(n-1)}{2} = \dfrac{n^2 - n}{2}$ . The dominant term is $n^2$ ; constants and the $-n$ are discarded.

Step 4: State the complexity

The time complexity is $O(n^2)$ . The extra space is $O(1)$ , since only loop counters are used regardless of input size.

Examples in context

Example 1. Why search engines do not scan everything. A linear scan of billions of web pages per query would be $O(n)$ in the size of the index - far too slow. Search engines build indexes that allow near- $O(\log n)$ or constant-time lookups, which is the whole reason results return in milliseconds.

Example 2. Choosing a sort in practice. A teaching example might use bubble sort ( $O(n^2)$ ) for clarity, but a library sorting a million records uses an $O(n \log n)$ algorithm. The difference is not academic: at $n = 10^6$ , the quadratic version does roughly a trillion operations versus about twenty million for $n \log n$ .

Try this

Q1. State the Big-O time complexity of summing all elements of a list of $n$ numbers. [1 mark]

Cue. $O(n)$ - one pass adds each element once.

Q2. Reduce $O(4n^2 + 2n + 7)$ to standard Big-O form. [1 mark]

Cue. $O(n^2)$ - keep only the dominant term, drop constants and lower-order terms.

Q3. An algorithm halves its input each step. State and justify its time complexity. [2 marks]

Cue. $O(\log n)$ - the number of steps is the number of times $n$ can be halved, which is $\log_2 n$ .

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original5 marksState the Big-O time complexity of each of the following and justify briefly: (a) finding the maximum of an unsorted list of

n

items; (b) a nested loop where the outer runs

n

times and the inner runs

n

times; (c) binary search on a sorted list of

n

items.

Show worked answer →

(a) $O(n)$ . You must inspect every element once to be sure of the maximum, so the work grows linearly with $n$ .

(b) $O(n^2)$ . The inner loop runs $n$ times for each of the $n$ outer iterations, giving $n \\times n = n^2$ basic operations.

(c) $O(\\log n)$ . Binary search halves the search range each step, so the number of steps is the number of times $n$ can be halved, which is $\\log_2 n$ .

Markers reward each correct class with a one-line justification: linear because every item is seen once, quadratic because of the nested loop, logarithmic because the range halves.

Original5 marksTwo algorithms solve the same problem: Algorithm A runs in

O(n^2)

time using

O(1)

extra space; Algorithm B runs in

O(n \log n)

time using

O(n)

extra space. (a) Which is faster for very large

n

, and why? (b) Give a situation where you might still prefer Algorithm A. (c) Explain what

O(1)

space means.

Show worked answer →

(a) Algorithm B is faster for very large $n$ , because $n \\log n$ grows much more slowly than $n^2$ ; as $n$ increases the quadratic term dominates and A's running time pulls far ahead of B's.

(b) You might prefer A when memory is very tight or $n$ is small. A uses only constant extra space, so on a device with little memory, or for small inputs where the constant factors make A competitive, A can be the better choice.

(c) $O(1)$ space means the extra memory used does not grow with the input size - the algorithm needs only a fixed number of variables regardless of how large $n$ is.

Markers reward identifying B as asymptotically faster with the growth-rate reason, a valid trade-off favouring A (low memory or small n), and a correct definition of constant space.