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 log n) - At each split step the algorithm allocates n amount of space so the total space is n times the number of splits
-
B
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
-
C
O(n^n) - Each split step takes up n amount of space and with a total of n splits, exponential space is needed