Order of complexity and Big-O notation

Overview

Recall questions on constant, logarithmic, linear, polynomial and exponential growth, and on deriving an algorithm's complexity from its code.

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

   What does Big-O notation express?

   Model answer

   Big-O notation expresses how an algorithm’s requirements grow as the size of the problem grows — most often its running time, though the same notation describes the memory it needs. It names the shape of the growth rather than an exact number of operations, so it describes the algorithm itself independently of the machine it runs on.

2. 2

   Name the five orders of growth you must be able to recognise, in increasing order of how badly they grow.

   Model answer

   Constant time O(1), logarithmic time O(log n), linear time O(n), polynomial time such as O(n²), and exponential time such as O(2ⁿ).

3. 3

   What does constant time mean, and give two examples?

   Model answer

   Constant time, O(1), means the running time does not depend on the size of the problem at all — the same amount of work is done whether there are ten items or ten million. Reading the element at a given index of an array is O(1), because the address is calculated directly from the index. Pushing an item onto a stack held as an array with a top pointer is O(1), because it writes one item and adjusts one pointer regardless of how many items are already there.

4. 4

   What does logarithmic time mean, and give an example with numbers?

   Model answer

   Logarithmic time, O(log n), means that each step disposes of a fixed fraction of what remains, so the work grows extremely slowly with problem size. Binary search on a list of 1000 items needs at most about 10 comparisons, because each comparison halves the range and 2¹⁰ = 1024; doubling the list to 2000 items adds just one more comparison. This holds only if the list is already sorted and any element can be reached directly by index.

5. 5

   What does linear time mean, and give an example?

   Model answer

   Linear time, O(n), means the running time grows in direct proportion to the size of the problem: double the data and the algorithm takes about twice as long. Finding the largest value in an unsorted list of n items is O(n), because every item must be examined once and no fewer would do. Linear search is also O(n) in the worst case, examining all n items when the target is last or absent.

6. 6

   What does polynomial time mean, and give an example?

   Model answer

   Polynomial time means the running time grows as a fixed power of the problem size, such as O(n²) or O(n³). Bubble sort is O(n²): it makes about n passes and each pass makes about n comparisons, so doubling the number of items multiplies the work by roughly four. Comparing every item in a list with every other item is likewise O(n²), and comparing every triple would be O(n³).

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.