- Merge Sort 8:07
- Splitting Into Sublists 3:14
- Recursively Merging Sublists 7:07
- Merge Sort Implementations
- Recap: Merge Sort 3 questions
- Ensuring the Correctness of Merge Sort 6:41
- Evaluating the Runtime of Merge Sort 7:22
- Alternate Versions of Merge Sort
- Recap: Runtime Analysis of Merge Sort 4 questions
Well done!
You have completed Recap: Runtime Analysis of Merge Sort!
Quiz Question 1 of 4
What is the space complexity of the merge sort algorithm?
Choose the correct answer below:
-
A
O(n) - Even though each split step allocates n amount of space, they steps don't occur simultaneously and at most only n amount of memory is needed
-
B
O(n^n) - Each split step takes up n amount of space and with a total of n splits, exponential space is needed
-
C
O(n log n) - At each split step the algorithm allocates n amount of space so the total space is n times the number of splits