The common complexity classes

Overview

O(log n) algorithm, O(n) algorithm and O(n log n) algorithm.

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

   State the complexity of an algorithm whose running time does not depend on the size of the input.

   Model answer

   An algorithm whose running time is independent of n is O(1). The class is called constant time.

2. 2

   Give an example of an O(1) operation.

   Model answer

   Reading the element at a known index of an array is O(1). The position is calculated directly, so the array's length makes no difference.

3. 3

   What growth does O(log n) describe?

   Model answer

   O(log n) describes logarithmic growth, where the work rises by one step each time the data doubles.

4. 4

   Give an example of an O(log n) algorithm.

   Model answer

   A binary search on an ordered list is O(log n). Each comparison discards half the remaining items.

5. 5

   What growth does O(n) describe?

   Model answer

   O(n) describes linear growth, where the work rises in direct proportion to the size of the input.

6. 6

   Give an example of an O(n) algorithm.

   Model answer

   A linear search through an unordered list is O(n). Every item may have to be examined once.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.