Space complexity and sorting in place

Overview

Space complexity of a bubble sort, space complexity of an insertion sort and space complexity of a quicksort.

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 it mean to say a sorting algorithm works in place?

   Model answer

   An in-place algorithm rearranges the data within the original array. Only a fixed small amount of extra memory is needed.

2. 2

   State the space complexity of a bubble sort.

   Model answer

   A bubble sort is O(1) in space. The algorithm needs only one temporary variable to hold a value during a swap.

3. 3

   State the space complexity of an insertion sort.

   Model answer

   An insertion sort is O(1) in space, because the item being placed is held in one temporary variable.

4. 4

   State the space complexity of a quicksort.

   Model answer

   A quicksort partitions in place but needs stack space for its recursive calls. The space complexity is O(log n) on average.

5. 5

   Why does a recursive algorithm consume memory even when it stores no new data?

   Model answer

   Each recursive call places a stack frame on the call stack holding its parameters and return address. The frames are only released as the calls unwind.

6. 6

   What is the space complexity of a quicksort in its worst case?

   Model answer

   The worst case is O(n), because the recursion reaches a depth of n when every partition is maximally unbalanced.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.