Measuring efficiency and Big O notation

Overview

Recall questions on why timing is a poor measure, Big O notation, time and space complexity, constant, logarithmic, linear, polynomial and exponential complexity, estimating run times, ordering complexities, best, average and worst cases, and sorting in place.

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

   Why is timing an algorithm with a stopwatch a poor way to measure its efficiency?

   Model answer

   The time measured depends on the processor speed, the amount of memory, the language, the compiler and what else the machine is doing, so the same algorithm gives different times on different machines. It also only tells you about the one data set used. Counting the number of key operations as the size of the input grows gives a measure that is a property of the algorithm itself.

2. 2

   What does Big O notation actually describe?

   Model answer

   How the resources an algorithm needs grow as the size of its input, n, grows. It gives an upper bound on that growth, expressed as the dominant term with constants and lower-order terms discarded, so it describes the shape of the growth rather than an exact number of operations.

3. 3

   Distinguish between time complexity and space complexity.

   Model answer

   Time complexity describes how the number of operations grows with the size of the input. Space complexity describes how the amount of memory needed grows with the size of the input, usually counting the extra memory the algorithm needs on top of the input itself. An algorithm can be excellent on one and poor on the other.

4. 4

   An algorithm performs 3n squared plus 20n plus 7 operations. What is its Big O complexity and why?

   Model answer

   O(n squared). As n grows the n squared term dominates completely: at n = 1000 it contributes three million while 20n contributes twenty thousand and the 7 is irrelevant. Big O keeps only the fastest-growing term and drops the constant multiplier, because those affect the size of the numbers, not the shape of the growth.

5. 5

   Define constant complexity and give an example.

   Model answer

   O(1). The time taken does not depend on the amount of data at all: the same number of steps is performed whether there are ten items or ten million. Examples are reading the item at a given index of an array, pushing an item onto a stack, and swapping two values.

6. 6

   Define logarithmic complexity and give an example.

   Model answer

   O(log n). Each step discards a fixed fraction of the remaining data, usually half, so the number of steps grows extremely slowly. The standard example is binary search on a sorted list; searching a well-balanced binary search tree behaves the same way.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.