Algorithmic efficiency and Big O notation

What Big O measures

Big O describes the upper bound on the growth rate of time (or memory) as the input size n increases. It keeps only the dominant term and ignores constants: 3n² + 5n + 20 is O(n²), because for large n the n² term swamps the rest.

It is needed to: compare algorithms independently of hardware; predict how a program will cope with much more data; choose a suitable algorithm; spot intractable problems.

The complexity classes

From slowest-growing to fastest-growing. The last column shows how many steps each needs for 1000 items.

Polynomial also includes n³ and higher powers

Best and worst cases

Exam questions often ask for both. The worst case is what Big O usually quotes.

Finding the Big O of code

• A single statement: O(1).
• A loop over n items: O(n). Two loops one after the other: O(n) + O(n) = O(n).
• A loop nested inside another, each over n: O(n²); three deep: O(n³).
• A loop that halves (or doubles) its range each pass: O(log n).
• A loop over n containing a halving loop: O(n log n).
• Recursion that makes two calls on n - 1 each time: O(2ⁿ).

for i in range(n):          # n times
    for j in range(n):      # n times each
        total += i * j      # O(1)
# O(n^2)

while n > 1:                # halves each time
    n = n // 2
# O(log n)

Worked example

A sorting algorithm takes 2 seconds for 1000 items and is O(n²). Estimate the time for 3000 items.

1. n is multiplied by 3.
2. For O(n²), time is multiplied by 3² = 9.
3. 2 x 9 = 18 seconds.

Answer: About 18 seconds

Check yourself

1. What is the Big O of an algorithm whose number of steps is 4n² + 10n + 7?
   • O(4n²)
   • O(n)
   • O(n²)
   • O(n² + n)
   Show answer

   O(n²). Keep the dominant term and drop constants.

2. What is the worst-case time complexity of binary search?
   • O(log n)
   • O(n)
   • O(1)
   • O(n log n)
   Show answer

   O(log n). Each comparison halves the remaining items.

3. What is the time complexity of a loop over n items nested inside another loop over n items, with O(1) work inside?
   • O(2n)
   • O(n log n)
   • O(n²)
   • O(log n)
   Show answer

   O(n²). n x n iterations.

4. What is the time complexity of: while n > 1: n = n // 2?
   • O(n)
   • O(log n)
   • O(n²)
   • O(1)
   Show answer

   O(log n). The number of passes is about log2 n.

5. What is the maximum number of comparisons binary search needs for a sorted list of 1000 items?
   Show answer

   10. 2⁹ = 512 < 1000 <= 1023 = 2¹⁰ - 1, so at most 10 comparisons.

6. An O(n²) algorithm takes 5 ms for 200 items. Estimate the time for 800 items, in ms.
   Show answer

   80 ms. n x 4, so time x 16: 5 x 16 = 80 ms.

7. Merge sort makes about n log2 n comparisons. Estimate this for n = 1024.
   Show answer

   10240. 1024 x 10 = 10 240.

8. Which statement describes linear time, O(n)?
   • The running time stays the same however many items there are
   • The running time doubles with each extra item
   • The running time grows in direct proportion to the number of items
   • The running time grows with the square of the number of items
   Show answer

   The running time grows in direct proportion to the number of items. Double the data, double the time.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.