Lesson 4.4.4.3

4.4.4.3 Order of complexity Quiz: AQA Computer Science, Unit 4

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.4.4.3, Order of complexity: 20 multiple choice questions for the AQA Computer Science (7517), Unit 4: Theory of computation, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. What is the Big-O notation for constant time?

    • O(n^2)
    • O(1)
    • O(n)
    • O(log n)

  2. Binary search is an example of which order of complexity?

    • Logarithmic time
    • Exponential time
    • Constant time
    • Linear time

  3. Linear search is an example of which order of complexity?

    • Exponential time
    • Logarithmic time
    • Constant time
    • Linear time

  4. Bubble sort is an example of which order of complexity?

    • Polynomial time, quadratic in this case
    • Logarithmic time
    • Linear time
    • Constant time

  5. Which algorithm has exponential time complexity?

    • An algorithm that checks every subset of n items
    • An algorithm that reads each item once
    • An algorithm that halves its input each step
    • An algorithm that accesses one array element

  6. Which growth class is fastest-growing among O(n), O(log n), O(n^2) and O(2^n)?

    • O(log n)
    • O(n)
    • O(2^n)
    • O(n^2)

  7. A loop runs once for each value of i from 1 to n, with a constant amount of work each time. What is the complexity?

    • O(n)
    • O(n^2)
    • O(log n)
    • O(1)

  8. Two nested loops each run from 1 to n with constant work in the body. What is the complexity?

    • O(n)
    • O(n^2)
    • O(log n)
    • O(2^n)

  9. A loop doubles i each iteration from 1 until it reaches n. What is the complexity?

    • O(n)
    • O(log n)
    • O(n^2)
    • O(1)

  10. The inner loop runs i times for i from 1 to n. What is the total number of inner iterations?

    • n
    • n(n + 1) / 2
    • 2^n
    • log n

  11. Which Big-O expression describes 3n^2 + 5n + 2?

    • O(n^2)
    • O(2^n)
    • O(n^3)
    • O(n)

  12. Which Big-O expression describes 7n log n + 100?

    • O(n)
    • O(log n)
    • O(n^2)
    • O(n log n)

  13. Which function grows faster as n tends to infinity?

    • Neither grows
    • n^3
    • 1000n^2
    • They grow at the same rate

  14. An algorithm runs in O(2^n) time. Roughly how many steps does it need for n = 20?

    • About 1 million
    • 20
    • 400
    • About 1 billion

  15. Why does Big-O notation ignore constant factors?

    • Because constants are always zero
    • Because it describes the growth rate as the input becomes large
    • Because constants never affect running time
    • Because Big-O only applies to strings

  16. When n doubles, how does the running time of an O(log n) algorithm change?

    • It doubles
    • It is unchanged
    • It increases by a fixed amount
    • It quadruples

  17. How many permutations are there of 5 distinct items?

    • 120
    • 3125
    • 60
    • 24

  18. Which statement about n! is correct?

    • It grows faster than any fixed exponential c^n for large n
    • It is a logarithmic function
    • It is always equal to n squared
    • It grows more slowly than n^2

  19. Which statement is true for large n?

    • n log n grows faster than n^1.5
    • n^1.5 is O(n log n)
    • n log n is O(n^1.5)
    • They grow identically

  20. What is the Big-O of an algorithm that takes n + log n steps?

    • O(n^2)
    • O(2^n)
    • O(log n)
    • O(n)

All AQA Computer Science quizzes