Question

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

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(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(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 complexity: O(n)

Answer 1

The correct answer for the time and space complexities of the merge sort algorithm is:

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

### Explanation:

1. **Time Complexity:**
- Merge sort divides the array into halves, which takes O(log n) time due to the recursive division.
- Merging the two halves takes O(n) time.
- Therefore, the overall time complexity is O(n log n).

2. **Space Complexity:**
- Merge sort requires additional space to hold the merged array, which is proportional to the size of the input array.
- Therefore, the space complexity is O(n) due to the temporary arrays used in the merge process.

Thus, the final answer is:

- Time complexity: O(n log n)
- Space complexity: O(n)