Deriving the complexity of a given algorithm

Overview

Reading Big O off the code: a single loop, nested loops, loops in sequence, a halving loop, and the rule that the most expensive part decides the whole.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   How is the complexity of a single loop that runs n times found?

   Model answer

   A single loop over n items performs a constant amount of work n times. The complexity is O(n).

2. 2

   State the complexity of a loop nested inside another loop, each running n times.

   Model answer

   The inner body runs n × n times, so the complexity is O(n²).

3. 3

   State the complexity of three loops nested one inside another, each running n times.

   Model answer

   The body runs n³ times, so the complexity is O(n³).

4. 4

   What is the complexity of two loops placed one after the other, each running n times?

   Model answer

   The total work is n + n, which is 2n. Constants are dropped, so the complexity is O(n).

5. 5

   State the complexity of a loop that halves a counter on every pass until it reaches one.

   Model answer

   The number of passes is log₂ n, so the complexity is O(log n).

6. 6

   What is the complexity of a loop running n times whose body contains a binary search?

   Model answer

   The complexity is O(n log n), because a log n operation is performed n times.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.