Question

Determine the time and space complexities of a merge sort.(1 point)
Responses

time complexity: O(n⋅log(n))

space complexity: O(n⋅log(n))
time complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis space complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis

time complexity: O(n)

space complexity: O(n⋅log(n))
time complexity: upper O left parenthesis n right parenthesis space complexity: upper O left parenthesis n times log left parenthesis n right parenthesis right parenthesis

time complexity: O(n2)

space complexity: O(n)
time complexity: upper O left parenthesis n squared right parenthesis space complexity: upper O left parenthesis n right parenthesis

time complexity: O(n⋅log(n))

space

Answer 1

The correct time and space complexities for the merge sort algorithm are as follows:

- **Time Complexity:** O(n log n)
- **Space Complexity:** O(n)

### Explanation:

1. **Time Complexity:**
- Merge sort works by dividing the array into halves recursively until each sub-array contains a single element (log n divisions). Then, it merges the sub-arrays back together in a sorted manner, which takes linear time (O(n)) for each level of recursion. Thus, the overall time complexity is O(n log n).

2. **Space Complexity:**
- Merge sort requires additional space to hold the temporary arrays during the merging process. This space is proportional to the size of the input array, leading to a space complexity of O(n).

Therefore, the appropriate answer would be:

- **Time Complexity:** O(n log n)
- **Space Complexity:** O(n)